Gallai–Hasse–Roy–Vitaver theorem

In graph theory, the Gallai–Hasse–Roy–Vitaver theorem is a form of duality between the colorings of the vertices of a given undirected graph and the orientations of its edges. It states that the minimum number of colors needed to properly color any graph ${\displaystyle G}$ equals one plus the length of a longest path in an orientation of ${\displaystyle G}$ chosen to minimize this path's length. The orientations for which the longest path has minimum length always include at least one acyclic orientation.

This theorem implies that every orientation of a graph with chromatic number ${\displaystyle k}$ contains a simple directed path with ${\displaystyle k}$ vertices; this path can be constrained to begin at any vertex that can reach all other vertices of the oriented graph.