Gallai-Roy theorem
From Egres Open
Theorem (Gallai [1], Roy [2]). In a directed graph D, the length of the longest directed path is at least the chromatic number of (the underlying undirected graph of) D.
A special case is Rédei's theorem [3]: every tournament contains a Hamiltonian path.
References
- ↑ T. Gallai, On directed paths and circuits, in: Theory of Graphs, (P. Erdős and G. Katona, eds.), Academic Press, New York, 1968, 115-118.
- ↑ B. Roy, Nombre chromatique et plus longs chemins, Rev. F1, Automat. Informat. 1 (1976), 127-132, EuDML link
- ↑ L. Rédei, Ein kombinatorischer satz, Acta Litt. Sci. Szeged, 7 (1934-35) 39-43.
