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.

equals one plus the length of a longest path in an orientation of

[2] This theorem implies that every orientation of a graph with chromatic number

The longest path in this orientation has length one, with 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.

[6] 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.

[7] Correspondingly, the chromatic number of an odd cycle is three.

[8] To prove that the chromatic number is greater than or equal to the minimum number of vertices in a longest path, suppose that a given graph has a coloring with

[3] To prove that the chromatic number is less than or equal to the minimum number of vertices in a longest path, suppose that a given graph has an orientation with at most

vertices per simple directed path, for some number

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.

[1] The proof of this theorem was used as a test case for a formalization of mathematical induction by Yuri Matiyasevich.

In particular, the coloring given by the length of the longest incoming path corresponds in this way to a homomorphism to a transitive tournament (an acyclically oriented complete graph), and every coloring can be described by a homomorphism to a transitive tournament in this way.

Thus, the Gallai–Hasse–Roy–Vitaver theorem can be equivalently stated as follows:For every directed graph

is acyclic, this can also be seen as a form of Mirsky's theorem that the longest chain in a partially ordered set equals the minimum number of antichains into which the set may be partitioned.

[10] This statement can be generalized from paths to other directed graphs: for every polytree

[2] It is named after separate publications by Tibor Gallai,[12] Maria Hasse,[13] B. Roy,[14] and L. M.

[15] Roy credits the statement of the theorem to a conjecture in a 1958 graph theory textbook by Claude Berge.

[14] It is a generalization of a much older theorem of László Rédei from 1934, that every tournament (an oriented complete graph) contains a directed Hamiltonian path.

[16] Instead of orienting a graph to minimize the length of its longest path, it is also natural to maximize the length of the shortest path, for a strong orientation (one in which every pair of vertices has a shortest path).

For these graphs, it is always possible to find a strong orientation in which, for some pair of vertices, the shortest path length equals the length of the longest path in the given undirected graph.