information:classification
Incomparable graphs

There are many incomparable graphs with respect to the homomorphism preorder, that is, pairs of graphs such that neither admits a homomorphism into the other. One way to construct them is to consider the odd girth of a graph G, the length of its shortest odd-length cycle.The odd girth is, equivalently, the smallest odd number g for which there exists a homomorphism from the cycle graph on g vertices to G. For this reason, if G → H, then the odd girth of G is greater than or equal to the odd girth of H.

On the other hand, if G → H, then the chromatic number of G is less than or equal to the chromatic number of H. Therefore, if G has strictly larger odd girth than H and strictly larger chromatic number than H, then G and H are incomparable. For example, the Grötzsch graph is 4-chromatic and triangle-free (it has girth 4 and odd girth 5), so it is incomparable to the triangle graph K.

Examples of graphs with arbitrarily large values of odd girth and chromatic number are Kneser graphs and generalized Mycielskians. A sequence of such graphs, with simultaneously increasing values of both parameters, gives infinitely many incomparable graphs (an antichain in the homomorphism preorder). Other properties, such as density of the homomorphism preorder, can be proved using such families. Constructions of graphs with large values of chromatic number and girth, not just odd girth, are also possible, but more complicated (see Girth and graph coloring).

Among directed graphs, it is much easier to find incomparable pairs. For example, consider the directed cycle graphs C →, with vertices 1, 2, …, n and edges from i to i + 1 (for i = 1, 2, …, n − 1) and from n to 1.There is a homomorphism from C → to C → (n, k ≥ 3) if and only if n is a multiple of k. In particular, directed cycle graphs C → with n prime are all incomparable.