Editing Graph homomorphism (section)

===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]].