Editing Graph homomorphism (section)

==Structure of homomorphisms==
Compositions of homomorphisms are homomorphisms.{{sfn|Hell|Nešetřil|2004|loc=§1.7}} 
In particular, the relation → on graphs is transitive (and reflexive, trivially), so it is a [[preorder]] on graphs.{{sfn|Hell|Nešetřil|2004|loc=§3.1}}
Let the [[equivalence class]] of a graph ''G'' under [[homomorphic equivalence]] be [''G''].
The equivalence class can also be represented by the unique core in [''G''].
The relation → is a [[partial order]] on those equivalence classes; it defines a [[poset]].{{sfn|Hell|Nešetřil|2004|loc=Theorem 3.1}}

Let ''G'' < ''H'' denote that there is a homomorphism from ''G'' to ''H'', but no homomorphism from ''H'' to ''G''.
The relation → is a [[dense order]], meaning that for all (undirected) graphs ''G'', ''H'' such that ''G'' < ''H'', there is a graph ''K'' such that ''G'' < ''K'' < ''H'' (this holds except for the trivial cases ''G'' = ''K''<sub>0</sub> or ''K''<sub>1</sub>).{{sfnm|1a1=Hell|1a2=Nešetřil|1y=2004|1loc=Theorem 3.30|2a1=Hahn|2a2=Tardif|2y=1997|2loc=Theorem 2.33}}<ref>{{citation|first=E.|last=Welzl|title=Color-families are dense|year=1982|journal=[[Theoretical Computer Science (journal)|Theoretical Computer Science]]|volume=17|pages=29–41|doi=10.1016/0304-3975(82)90129-3|doi-access=free}}</ref>
For example, between any two [[complete graph]]s (except ''K''<sub>0</sub>, ''K''<sub>1</sub>, ''K''<sub>2</sub>) there are infinitely many [[circular clique|circular complete graphs]], corresponding to rational numbers between natural numbers.{{sfnm|1a1=Hell|1a2=Nešetřil|1y=2004|1p=192|2a1=Hahn|2a2=Tardif|2y=1997|2p=127}}

The poset of equivalence classes of graphs under homomorphisms is a [[distributive lattice]], with the [[Join and meet|join]] of  [''G''] and  [''H''] defined as (the equivalence class of) the disjoint union [''G'' ∪ ''H''], and the [[Join and meet|meet]] of [''G''] and  [''H''] defined as the [[tensor product of graphs|tensor product]] [''G'' × ''H''] (the choice of graphs ''G'' and ''H'' representing the equivalence classes [''G''] and [''H''] does not matter).<ref>{{harvnb|Hell|Nešetřil|2004|loc=Proposition 3.2}}, distributivity is stated in Proposition 2.4; {{harvnb|Hahn|Tardif|1997|loc=Theorem 2.37}}.</ref>
The [[join-irreducible]] elements of this lattice are exactly [[Connectivity (graph theory)|connected]] graphs. This can be shown using the fact that a homomorphism maps a connected graph into one connected component of the target graph.<ref>{{citation
 | last1 = Kwuida | first1 = Léonard
 | last2 = Lehtonen | first2 = Erkko
 | title = On the Homomorphism Order of Labeled Posets
 | doi = 10.1007/s11083-010-9169-x
 | year = 2011
 | arxiv = 0911.0200
 | journal = [[Order (journal)|Order]]
 | volume = 28
 | issue = 2
 | pages = 251–265
 | s2cid = 14920600
 }}</ref>{{sfn|Gray|2014|loc=Lemma 3.7}}
The [[meet-irreducible]] elements of this lattice are exactly the [[Hedetniemi's conjecture#multiplicative graphs|multiplicative graphs]]. These are the graphs ''K'' such that a product ''G'' × ''H'' has a homomorphism to ''K'' only when one of ''G'' or ''H'' also does. Identifying multiplicative graphs lies at the heart of [[Hedetniemi's conjecture]].<ref>{{citation
 | last = Tardif
 | first = C.
 | title = Hedetniemi's conjecture, 40 years later
 | url = http://www.mast.queensu.ca/~ctardif/articles/gtn5406rp.pdf
 | pages = 46–57
 | volume = 54
 | journal = Graph Theory Notes of New York
 | mr = 2445666
 | year = 2008
 | access-date = 2017-08-05
 | archive-date = 2021-07-12
 | archive-url = https://web.archive.org/web/20210712104609/https://mast.queensu.ca/~ctardif/articles/gtn5406rp.pdf
 | url-status = dead
 }}.</ref><ref name="lattices">{{citation|first1=D.|last1=Duffus|first2=N.|last2=Sauer|title=Lattices arising in categorial investigations of Hedetniemi's conjecture|journal=[[Discrete Mathematics (journal)|Discrete Mathematics]]|volume=152|issue=1–3|year=1996|pages=125–139|doi=10.1016/0012-365X(94)00298-W|doi-access=free}}</ref>

Graph homomorphisms also form a [[category (mathematics)|category]], with graphs as objects and homomorphisms as arrows.{{sfn|Hell|Nešetřil|2004|p=125}}
The [[Initial and terminal objects|initial object]] is the empty graph, while the [[Initial and terminal objects|terminal object]] is the graph with one vertex and one [[Loop (graph theory)|loop]] at that vertex.
The [[tensor product of graphs]] is the [[Product (category theory)|category-theoretic product]] and 
the [[Hedetniemi's conjecture#Exponential graph|exponential graph]] is the [[exponential object]] for this category.<ref name="lattices"/>{{sfn|Gray|2014}}
Since these two operations are always defined, the category of graphs is a [[cartesian closed category]].
For the same reason, the lattice of equivalence classes of graphs under homomorphisms is in fact a [[Heyting algebra]].<ref name="lattices"/>{{sfn|Gray|2014}}

For directed graphs the same definitions apply. In particular → is a [[partial order]] on equivalence classes of directed graphs. It is distinct from the order → on equivalence classes of undirected graphs, but contains it as a suborder. This is because every undirected graph can be thought of as a directed graph where every arc (''u'',''v'') appears together with its inverse arc (''v'',''u''), and this does not change the definition of homomorphism. The order → for directed graphs is again a distributive lattice and a Heyting algebra, with join and meet operations defined as before. However, it is not dense. There is also a category with directed graphs as objects and homomorphisms as arrows, which is again a [[cartesian closed category]].{{sfn|Brown|Morris|Shrimpton|Wensley|2008}}{{sfn|Gray|2014}}

===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}}