<script type="text/javascript">
<!--
document.write('<div id="oa_widget"></div>');
document.write('<script type="text/javascript" src="https://www.openaire.eu/index.php?option=com_openaire&view=widget&format=raw&projectId=undefined&type=result"></script>');
-->
</script>
We consider the colouring (or homomorphism) order C induced by all finite graphs and the existence of a homomorphism between them. This ordering may be seen as a lattice which is however far from being complete. In this paper we study bounds, suprema and maximal elements in C of some frequently studied classes of graphs (such as bounded degree, degenerated and classes determined by a finite set of forbidden subgraphs). We relate these extrema to cuts of subclasses K of C (cuts are finite sets which are comparable to every element of the class K). We determine all cuts for classes of degenerated graphs. For classes of bounded degree graphs this seems to be a very difficult problem which is also mirrored by the fact that these classes fail to have a supremum. We note a striking difference between undirected and oriented graphs. This is based on the recent work of C. Tardif and J. Nesetril. Also minor closed classes are considered and we survey recent results obtained by authors. A bit surprisingly this order setting captures Hadwiger conjecture and suggests some new problems.
Homomorphism order, Cuts, Graph minors, Theoretical Computer Science, Graph theory, Combinatorics of partially ordered sets, [MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO], Coloring of graphs and hypergraphs, Partial orders, general, Bounds, Algebraic combinatorics, Homomorphism, Discrete Mathematics and Combinatorics, Homomorphism extrema
Homomorphism order, Cuts, Graph minors, Theoretical Computer Science, Graph theory, Combinatorics of partially ordered sets, [MATH.MATH-CO] Mathematics [math]/Combinatorics [math.CO], Coloring of graphs and hypergraphs, Partial orders, general, Bounds, Algebraic combinatorics, Homomorphism, Discrete Mathematics and Combinatorics, Homomorphism extrema
citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 11 | |
popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |