Editing Graph homomorphism (section)

===Incomparable graphs===
[[File:Groetzsch-graph.svg|thumb|upright=0.8|right|The Grötzsch graph, incomparable to ''K''<sub>3</sub>]]
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.{{sfn|Hell|Nešetřil|2004|p=7}}
One way to construct them is to consider the [[Girth (graph theory)|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''.{{sfn|Hahn|Tardif|1997|loc=Observation 2.6}}

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.{{sfn|Hell|Nešetřil|2004|p=7}}
For example, the [[Grötzsch graph]] is 4-chromatic and triangle-free (it has girth 4 and odd girth 5),<ref>{{mathworld | title = Grötzsch Graph | urlname = GroetzschGraph|mode=cs2}}</ref> so it is incomparable to the triangle graph ''K''<sub>3</sub>.

Examples of graphs with arbitrarily large values of odd girth and chromatic number are [[Kneser graph]]s{{sfn|Hahn|Tardif|1997|loc=Proposition 3.14}} and [[Mycielskian#Cones over graphs|generalized Mycielskians]].<ref>{{citation|
title=On Graphs With Strongly Independent Color-Classes|
first1=A.|last1=Gyárfás|first2=T.|last2=Jensen|first3=M.|last3=Stiebitz|
year=2004|doi=10.1002/jgt.10165|journal=[[Journal of Graph Theory]]|volume=46|issue=1|pages=1–14|
s2cid=17859655}}</ref>
A sequence of such graphs, with simultaneously increasing values of both parameters, gives infinitely many incomparable graphs (an [[antichain]] in the homomorphism preorder).{{sfn|Hell|Nešetřil|2004|loc=Proposition 3.4}}
Other properties, such as [[dense order|density]] of the homomorphism preorder, can be proved using such families.{{sfn|Hell|Nešetřil|2004|p=96}}
Constructions of graphs with large values of chromatic number and girth, not just odd girth, are also possible, but more complicated (see [[Girth (graph theory)#Girth and graph coloring|Girth and graph coloring]]).

Among directed graphs, it is much easier to find incomparable pairs. For example, consider the directed cycle graphs ''{{vec|C}}<sub>n</sub>'', 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 ''{{vec|C}}<sub>n</sub>'' to ''{{vec|C}}<sub>k</sub>'' (''n'', ''k'' ≥ 3) if and only if ''n'' is a multiple of ''k''. 
In particular, directed cycle graphs ''{{vec|C}}<sub>n</sub>'' with ''n'' prime are all incomparable.{{sfn|Hell|Nešetřil|2004|p=35}}