Gallai–Hasse–Roy–Vitaver theorem

Four different orientations of a 5-cycle, showing a maximal acyclic subgraph of each orientation (solid edges) and a coloring of the vertices by the length of the longest incoming path in this subgraph. The orientation with the shortest paths, on the left, also provides an optimal coloring of the graph.

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 a number k is the smallest number of colors among all colorings of graph G if and only if k is the largest number for which every orientation of G contains a simple directed path with k vertices.^[1] That is, the chromatic number is one plus the length of a longest path in an orientation of the graph chosen to minimize this path's length. The orientations for which the longest path has minimum length always include at least one acyclic orientation.^[2]

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;^[3] this path can be constrained to begin at any vertex that can reach all other vertices of the oriented graph.^[4][5]

Examples

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.

Proof

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.^[1]

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

Category-theoretic interpretation

The theorem also has a natural interpretation in the category of directed graphs and graph homomorphisms. A homomorphism is a map from the vertices of one graph to the vertices of another that always maps edges to edges. Thus, a k-coloring of an undirected graph G may be described by a homomorphism from G to the complete graph K_k. If the complete graph is given an orientation, it becomes a tournament, and the orientation can be lifted back across the homomorphism to given an orientation of G. 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.

Considering homomorphisms in the other direction, to G instead of from G, a directed graph G is acyclic and has at most k vertices in its longest path if and only if there is no homomorphism from the path graph P_k + 1 to G.

Thus, the Gallai–Hasse–Roy–Vitaver theorem is equivalent to the theorem that, for every directed graph G, there is a homomorphism to the k-vertex transitive tournament if and only if there is not a homomorphism from the (k + 1)-vertex path.^[2] In the case that G 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.^[7] This statement can be generalized from paths to other directed graphs: for every polytree P there is a dual directed graph D such that, for every directed graph G, there is a homomorphism from G to D if and only if there is not a homomorphism from P to G.^[8]

History

The Gallai–Hasse–Roy–Vitaver theorem has been repeatedly rediscovered.^[2] It is named after separate publications by Tibor Gallai,^[9] Maria Hasse,^[10] B. Roy,^[11] and L. M. Vitaver.^[12] Roy credits the statement of the theorem to a conjecture in a 1958 graph theory textbook by Claude Berge.^[11]

References

1. Hsu, Lih-Hsing; Lin, Cheng-Kuan (2009), "Theorem 8.5", Graph Theory and Interconnection Networks, Boca Raton, FL: CRC Press, pp. 129–130, ISBN 978-1-4200-4481-2, MR 2454502.
2. Nešetřil, Jaroslav; Ossona de Mendez, Patrice (2012), "Theorem 3.13", Sparsity: Graphs, Structures, and Algorithms, Algorithms and Combinatorics 28, Heidelberg: Springer, p. 42, doi:10.1007/978-3-642-27875-4, ISBN 978-3-642-27874-7, MR 2920058.
3. Chartrand, Gary; Zhang, Ping (2009), "Theorem 7.17 (The Gallai–Roy–Vitaver Theorem)", Chromatic Graph Theory, Discrete Mathematics and its Applications, Boca Raton, FL: CRC Press, ISBN 978-1-58488-800-0, MR 2450569.
4. Li, Hao (2001), "A generalization of the Gallai–Roy theorem", Graphs and Combinatorics 17 (4): 681–685, doi:10.1007/PL00007256, MR 1876576.
5. Chang, Gerard J.; Tong, Li-Da; Yan, Jing-Ho; Yeh, Hong-Gwa (2002), "A note on the Gallai–Roy–Vitaver theorem", Discrete Mathematics 256 (1-2): 441–444, doi:10.1016/S0012-365X(02)00386-2, MR 1927565.
6. Матиясевич, Ю. В. (1974), "Одна схема доказательств в дискретной математике" [A certain scheme for proofs in discrete mathematics], Исследования по конструктивной математике и математической логике [Studies in constructive mathematics and mathematical logic. Part VI. Dedicated to A. A. Markov on the occasion of his 70th birthday], Zapiski Naučnyh Seminarov Leningradskogo Otdelenija Matematičeskogo Instituta im. V. A. Steklova Akademii Nauk SSSR (LOMI) (in Russian) 40, pp. 94–100, MR 0363823.
7. Mirsky, Leon (1971), "A dual of Dilworth's decomposition theorem", American Mathematical Monthly 78 (8): 876–877, doi:10.2307/2316481, JSTOR 2316481.
8. Nešetřil, Jaroslav; Tardif, Claude (2008), "A dualistic approach to bounding the chromatic number of a graph", European Journal of Combinatorics 29 (1): 254–260, doi:10.1016/j.ejc.2003.09.024, MR 2368632.
9. Gallai, Tibor (1968), "On directed graphs and circuits", Theory of Graphs (Proceedings of the Colloquium Tihany 1966), New York: Academic Press, pp. 115–118. As cited by Nešetřil & Ossona de Mendez (2012).
10. Hasse, Maria (1965), "Zur algebraischen Begründung der Graphentheorie. I", Mathematische Nachrichten (in German) 28 (5–6): 275–290, doi:10.1002/mana.19650280503, MR 0179105.
11. Roy, B. (1967), "Nombre chromatique et plus longs chemins d'un graphe" (PDF), Rev. Française Informat. Recherche Opérationnelle (in French) 1 (5): 129–132, MR 0225683.
12. Витавер, Л. М. (1962), "Нахождение минимальных раскрасок вершин графа с помощью булевых степеней матрицы смежностей [Determination of minimal coloring of vertices of a graph by means of Boolean powers of the incidence matrix]", Doklady Akademii Nauk SSSR (in Russian) 147: 758–759, MR 0145509.