structural:summarization, stylistic:style_transfer, stylistic:tone
Orientations without long paths

Another interesting connection concerns 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 is the transitive tournament T → 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 H → of H can be pulled back to an orientation G → of G so that G → has a homomorphism to H →.Therefore, a graph G is k -colorable (has a homomorphism to K) if and only if some orientation of G has a homomorphism to T →.

A folklore theorem states that for all k, a directed graph G has a homomorphism to T → if and only if it admits no homomorphism from the directed path P →. Here P → 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 P →.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 P → as a subgraph). This is the Gallai–Hasse–Roy–Vitaver theorem.