Editing Graph homomorphism (section)

==Connection to colorings==
A [[graph coloring|''k''-coloring]], for some integer ''k'', is an assignment of one of ''k'' colors to each vertex of a graph ''G'' such that the endpoints of each edge get different colors. The ''k''-colorings of ''G'' correspond exactly to homomorphisms from ''G'' to the [[complete graph]] ''K''<sub>''k''</sub>.{{sfnm|1a1=Cameron|1y=2006|1p=1|2a1=Hell|2a2=Nešetřil|2y=2004|2loc=Proposition 1.7}} Indeed, the vertices of ''K''<sub>''k''</sub> correspond to the ''k'' colors, and two colors are adjacent as vertices of ''K''<sub>''k''</sub> if and only if they are different. Hence a function defines a homomorphism to ''K''<sub>''k''</sub> if and only if it maps adjacent vertices of ''G'' to different colors (i.e., it is a ''k''-coloring). In particular, ''G'' is ''k''-colorable if and only if it is ''K''<sub>''k''</sub>-colorable.{{sfnm|1a1=Cameron|1y=2006|1p=1|2a1=Hell|2a2=Nešetřil|2y=2004|2loc=Proposition 1.7}}

If there are two homomorphisms ''G'' → ''H'' and ''H'' → ''K''<sub>''k''</sub>, then their composition ''G'' → ''K''<sub>''k''</sub> is also a homomorphism.{{sfn|Hell|Nešetřil|2004|loc=§1.7}} In other words, if a graph ''H'' can be colored with ''k'' colors, and there is a homomorphism from ''G'' to ''H'', then ''G'' can also be ''k''-colored. Therefore, ''G'' → ''H'' implies χ(''G'') ≤  χ(''H''), where ''χ'' denotes the [[chromatic number]] of a graph (the least ''k'' for which it is ''k''-colorable).{{sfn|Hell|Nešetřil|2004|loc=Corollary 1.8}}

===Variants===
General homomorphisms can also be thought of as a kind of coloring: if the vertices of a fixed graph ''H'' are the available ''colors'' and edges of ''H'' describe which colors are ''compatible'', then an ''H''-coloring of ''G'' is an assignment of colors to vertices of ''G'' such that adjacent vertices get compatible colors.
Many notions of graph coloring fit into this pattern and can be expressed as graph homomorphisms into different families of graphs.
[[Circular coloring]]s can be defined using homomorphisms into [[circular clique|circular complete graph]]s, refining the usual notion of colorings.{{sfnm|1a1=Hell|1a2=Nešetřil|1y=2004|1loc=§6.1|2a1=Hahn|2a2=Tardif|2y=1997|2loc=§4.4}}
[[Fractional coloring|Fractional]] and [[Fractional coloring#Definitions|''b''-fold coloring]] can be defined using homomorphisms into [[Kneser graph]]s.{{sfnm|1a1=Hell|1a2=Nešetřil|1y=2004|1loc=§6.2|2a1=Hahn|2a2=Tardif|2y=1997|2loc=§4.5}}
[[T-coloring]]s correspond to homomorphisms into certain infinite graphs.{{sfn|Hell|Nešetřil|2004|loc=§6.3}}
An [[oriented coloring]] of a directed graph is a homomorphism into any [[oriented graph]].{{sfn|Hell|Nešetřil|2004|loc=§6.4}}
An [[L(2,1)-coloring]] is a homomorphism into the [[complement graph|complement]] of the [[path graph]] that is locally injective, meaning it is required to be injective on the neighbourhood of every vertex.<ref>{{citation|first1=J.|last1=Fiala|first2=J.|author2-link=Jan Kratochvíl|last2=Kratochvíl|s2cid=17507393|title=Partial covers of graphs|year=2002|journal=Discussiones Mathematicae Graph Theory|volume=22|issue=1|pages=89–99|doi=10.7151/dmgt.1159}}</ref>

===Orientations without long paths===
{{main|Gallai–Hasse–Roy–Vitaver theorem}}
Another interesting connection concerns [[Orientation (graph theory)|orientations]] of graphs.
An orientation of an undirected graph ''G'' is any directed graph obtained by choosing one of the two possible orientations for each edge.
An example of an orientation of the complete graph ''K<sub>k</sub>'' is the transitive tournament {{vec|{{var|T}}}}<sub>''k''</sub> with vertices 1,2,…,''k'' and arcs from ''i'' to ''j'' whenever ''i'' < ''j''.
A homomorphism between orientations of graphs ''G'' and ''H'' yields a homomorphism between the undirected graphs ''G'' and ''H'', simply by disregarding the orientations.
On the other hand, given a homomorphism ''G'' → ''H'' between undirected graphs, any orientation {{vec|{{var|H}}}} of ''H'' can be pulled back to an orientation {{vec|{{var|G}}}} of ''G'' so that {{vec|{{var|G}}}} has a homomorphism to {{vec|{{var|H}}}}.
Therefore, a graph ''G'' is ''k''-colorable (has a homomorphism to ''K<sub>k</sub>'') if and only if some orientation of ''G'' has a homomorphism to {{vec|{{var|T}}}}<sub>''k''</sub>.{{sfn|Hell|Nešetřil|2004|pp=13–14}}

A folklore theorem states that for all ''k'', a directed graph ''G'' has a homomorphism to {{vec|{{var|T}}}}<sub>''k''</sub> if and only if it admits no homomorphism from the directed path {{vec|{{var|P}}}}<sub>''k''+1</sub>.{{sfn|Hell|Nešetřil|2004|loc=Proposition 1.20}}
Here {{vec|{{var|P}}}}<sub>''n''</sub> is the directed graph with vertices 1, 2, …, ''n'' and edges from ''i'' to ''i'' + 1, for ''i'' = 1, 2, …, ''n'' − 1.
Therefore, a graph is ''k''-colorable if and only if it has an orientation that admits no homomorphism from {{vec|{{var|P}}}}<sub>''k''+1</sub>.
This statement can be strengthened slightly to say that a graph is ''k''-colorable if and only if some orientation contains no directed path of length ''k'' (no {{vec|{{var|P}}}}<sub>''k''+1</sub> as a subgraph). 
This is the [[Gallai–Hasse–Roy–Vitaver theorem]].