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 G equals one plus the length of a longest path in an orientation of 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.

An alternative statement of the same theorem is that every orientation of a graph with chromatic number k contains a simple directed path with k vertices; this path can be constrained to begin at any vertex that can reach all other vertices of the oriented graph.

A bipartite graph may be oriented from one side of the bipartition to the other; the longest path in this orientation has only two vertices. Conversely, if a graph is oriented without any three-vertex paths, then every vertex must either be a source (with no incoming edges) or a sink (with no outgoing edges) and the partition of the vertices into sources and sinks shows that it is bipartite.

In any orientation of a cycle graph of odd length, it is not possible for the edges to alternate in orientation all around the cycle, so some two consecutive edges must form a path with three vertices. Correspondingly, the chromatic number of an odd cycle is three.

To prove that the chromatic number is greater than or equal to the minimum length of a longest path, suppose that a given graph has a coloring with k colors, for some number k. Then it may be acyclically oriented by numbering colors and by directing each edge from its lower-numbered endpoint to the higher-numbered endpoint. With this orientation, the numbers are strictly increasing along each directed path, so each path can include at most one vertex of each color, for a total of at most k vertices per path.

To prove that the chromatic number is less than or equal to the minimum length of a longest path, suppose that a given graph has an orientation with at most k vertices per simple directed path, for some number k. Then the vertices of the graph may be colored with k colors by choosing a maximal acyclic subgraph of the orientation, and then coloring each vertex by the length of the longest path in the chosen subgraph that ends at that vertex. Each edge within the subgraph is oriented from a vertex with a lower number to a vertex with a higher number, and is therefore properly colored. For each edge that is not in the subgraph, there must exist a directed path within the subgraph connecting the same two vertices in the opposite direction, for otherwise the edge could have been included in the chosen subgraph; therefore, the edge is oriented from a higher number to a lower number and is again properly colored.

...
Wikipedia