Search

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 far from being complete. In this paper we study bounds and 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. Nešetřil. 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.

The oriented chromatic number o( H ) of an oriented graph H is defined as the minimum order of an oriented graph H ′ such that H has a homomorphism to H ′. The oriented chromatic number o( G ) of an undirected graph G is then defined as the maximum oriented chromatic number of its orientations. In this paper we study the links between o( G ) and mad( G ) defined as the maximum average degree of the subgraphs of G.

Let G = (V,E) be a directed graph, let M be an abelian group, and let f:E → M be a flow. We say that f is antisymmetric if f(E)∩-f(E)=O. Using a theorem of DeVos, Johnson, and Seymour, we improve upon a result of theirs by showing that every directed graph (without the obvious obstruction) has an antisymmetric flow in the group Z 3 3 x Z 6 6 . We also provide some additional theorems proving the existence of an antisymmetric flow in a smaller group, under the added assumption that G has a certain edge-connectivity.