Gallai–Hasse–Roy–Vitaver theorem

A bipartite graph may be oriented from one side of the bipartition to the other. 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 {{nowrap|bipartite.{{r|gh22}}}}

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.{{r|sridharan}} Correspondingly, the chromatic number of an odd cycle is three.{{r|odd-cycle}}

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 $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 {{nowrap|path.{{r|cz09}}}}

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 $k$ vertices per simple directed path, for some {{nowrap|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 {{nowrap|colored.{{r|hl09}}}}

The proof of this theorem was used as a test case for a formalization of mathematical induction by {{nowrap|Yuri Matiyasevich.{{r|matiyasevich}}}}

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 {{nowrap|$k$-coloring}} of an undirected {{nowrap|graph $G$}} may be described by a homomorphism from $G$ to the {{nowrap|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 give an orientation {{nowrap|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 {{nowrap|way.{{r|no12}}}}

Considering homomorphisms in the other direction, {{nowrap|to $G$}} instead of {{nowrap|from $G$,}} a directed {{nowrap|graph $G$}} has at most $k$ vertices in its longest path if and only if there is no homomorphism from the path graph $P\_\{k+1\}$ {{nowrap|to $G$.{{r|no12}}}}

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

For every directed {{nowrap|graph $G$,}} there is a homomorphism from $G$ to the {{nowrap|$k$-vertex}} transitive tournament if and only if there is no homomorphism from the {{nowrap|$(k+1)$-vertex}} path {{nowrap|to $G$.{{r|no12}}}}

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 {{nowrap|partitioned.{{r|mirsky}}}} This statement can be generalized from paths to other directed graphs: for every {{nowrap|polytree $P$}} there is a dual directed {{nowrap|graph $D$}} such that, for every directed {{nowrap|graph $G$,}} there is a homomorphism {{nowrap|from $G$}} {{nowrap|to $D$}} if and only if there is not a homomorphism {{nowrap|from $P$}} to {{nowrap|$G$.{{r|nt08}}}}

The Gallai–Hasse–Roy–Vitaver theorem has been repeatedly {{nowrap|rediscovered.{{r|no12}}}} It is named after separate publications by {{nowrap|Tibor Gallai,{{r|gallai}}}} {{nowrap|Maria Hasse,{{r|hasse}}}} {{nowrap|B. Roy,{{r|roy}}}} and {{nowrap|L. M. Vitaver.{{r|vitaver}}}} Roy credits the statement of the theorem to a conjecture in a 1958 graph theory textbook by {{nowrap|Claude Berge.{{r|roy}}}} 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.{{r|havet|redei}} Rédei's theorem follows immediately from the Gallai–Hasse–Roy–Vitaver theorem applied to an undirected complete graph.{{r|havet}}

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). Having a strong orientation requires that the given undirected graph be a bridgeless graph. 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 {{nowrap|graph.{{r|gutin|bondy}}}}

{{reflist|refs=

{{citation

| last = Bondy | first = J. A.

| doi = 10.1002/jgt.10135

| issue = 3

| journal = Journal of Graph Theory

| mr = 2012799

| pages = 159–165

| title = Short proofs of classical theorems

| volume = 44

| year = 2003| s2cid = 2174153

}}

{{citation

| last1 = Chang | first1 = Gerard J.

| last2 = Tong | first2 = Li-Da

| last3 = Yan | first3 = Jing-Ho

| last4 = Yeh | first4 = Hong-Gwa

| doi = 10.1016/S0012-365X(02)00386-2 | doi-access = free

| issue = 1–2

| journal = Discrete Mathematics

| mr = 1927565

| pages = 441–444

| title = A note on the Gallai–Roy–Vitaver theorem

| volume = 256

| year = 2002}}

{{citation

| last1 = Chartrand | first1 = Gary | author1-link = Gary Chartrand

| last2 = Zhang | first2 = Ping | author2-link = Ping Zhang (graph theorist)

| contribution = Theorem 7.17 (The Gallai–Roy–Vitaver Theorem)

| isbn = 978-1-58488-800-0

| location = Boca Raton, Florida

| mr = 2450569

| publisher = CRC Press

| series = Discrete Mathematics and its Applications

| title = Chromatic Graph Theory

| url = https://books.google.com/books?id=_l4CJq46MXwC&pg=PA190

| year = 2009}}

{{citation

| last = Gallai | first = Tibor | author-link = Tibor Gallai

| contribution = On directed graphs and circuits

| location = Budapest

| pages = 115–118

| publisher = Akadémiai Kiadó

| title = Theory of Graphs (Proceedings of the Colloquium held at Tihany 1966)

| year = 1968}}

{{citation

| last1 = Guzmán-Pro | first1 = Santiago

| last2 = Hernández-Cruz | first2 = César

| doi = 10.1016/j.ejc.2022.103567

| journal = European Journal of Combinatorics

| mr = 4432176

| at = Paper No. 103567

| title = Oriented expressions of graph properties

| volume = 105

| year = 2022| arxiv = 2012.12811

| s2cid = 229363421

}}

{{citation

| last = Gutin | first = G.

| doi = 10.1007/BF02986669

| issue = 3

| journal = Graphs and Combinatorics

| mr = 1304376

| pages = 225–230

| title = Minimizing and maximizing the diameter in orientations of graphs

| volume = 10

| year = 1994| s2cid = 2453716

}}

{{citation

| last = Hasse | first = Maria | authorlink = Maria Hasse

| doi = 10.1002/mana.19650280503

| issue = 5–6

| journal = Mathematische Nachrichten

| language = German

| mr = 0179105

| pages = 275–290

| title = Zur algebraischen Begründung der Graphentheorie. I

| volume = 28

| year = 1965}}

{{citation

| last = Havet | first = Frédéric

| contribution = Section 3.1: Gallai–Roy Theorem and related results

| pages = 15–19

| series = Lecture notes for the summer school SGT 2013 in Oléron, France

| title = Orientations and colouring of graphs

| url = https://oc.g-scop.grenoble-inp.fr/conf/sgt2013/oleron.pdf

| year = 2013}}

{{citation

| last1 = Hsu | first1 = Lih-Hsing

| last2 = Lin | first2 = Cheng-Kuan

| contribution = Theorem 8.5

| isbn = 978-1-4200-4481-2

| location = Boca Raton, Florida

| mr = 2454502

| pages = 129–130

| publisher = CRC Press

| title = Graph Theory and Interconnection Networks

| url = https://books.google.com/books?id=vbxdqhDKOSYC&pg=PA129

| year = 2009}}

{{citation

| last = Li | first = Hao

| doi = 10.1007/PL00007256

| issue = 4

| journal = Graphs and Combinatorics

| mr = 1876576

| pages = 681–685

| title = A generalization of the Gallai–Roy theorem

| volume = 17

| year = 2001| s2cid = 37646065

}}

{{citation

| last = Матиясевич | first = Ю. В. | author-link = Yuri Matiyasevich

| series = Zapiski Naučnyh Seminarov Leningradskogo Otdelenija Matematičeskogo Instituta im. V. A. Steklova Akademii Nauk SSSR (LOMI)

| language = Russian

| mr = 0363823

| pages = 94–100

| chapter-url=http://www.mathnet.ru/php/archive.phtml?wshow=paper&jrnid=znsl&paperid=2684

| chapter = Одна схема доказательств в дискретной математике

| trans-chapter = A certain scheme for proofs in discrete mathematics

| title = Исследования по конструктивной математике и математической логике

| trans-title = Studies in constructive mathematics and mathematical logic. Part VI. Dedicated to A. A. Markov on the occasion of his 70th birthday

| volume = 40

| year = 1974}}

{{citation

| authorlink = Leon Mirsky

| last = Mirsky | first = Leon

| title = A dual of Dilworth's decomposition theorem

| jstor = 2316481

| journal = American Mathematical Monthly

| volume = 78

| issue = 8 | year = 1971 | pages = 876–877

| doi = 10.2307/2316481}}

{{citation

| last1 = Nešetřil | first1 = Jaroslav | author1-link = Jaroslav Nešetřil

| last2 = Ossona de Mendez | first2 = Patrice | author2-link = Patrice Ossona de Mendez

| contribution = Section 3.7: Homomorphisms

| doi = 10.1007/978-3-642-27875-4

| isbn = 978-3-642-27874-7

| location = Heidelberg

| mr = 2920058

| pages = 39–46

| publisher = Springer

| series = Algorithms and Combinatorics

| title = Sparsity: Graphs, Structures, and Algorithms

| volume = 28

| year = 2012}}; see especially Theorem 3.13, p. 42

{{citation

| last1 = Nešetřil | first1 = Jaroslav | author1-link = Jaroslav Nešetřil

| last2 = Tardif | first2 = Claude

| doi = 10.1016/j.ejc.2003.09.024 | doi-access = free

| issue = 1

| journal = European Journal of Combinatorics

| mr = 2368632

| pages = 254–260

| title = A dualistic approach to bounding the chromatic number of a graph

| volume = 29

| year = 2008}}

More strongly, the graphs that require at least three colors (the non-bipartite graphs) are exactly the graphs that do not contain an odd cycle. This characterization is attributed to a 1916 paper of Dénes Kőnig by {{citation

| last1 = Asratian | first1 = Armen S.

| last2 = Denley | first2 = Tristan M. J.

| last3 = Häggkvist | first3 = Roland

| isbn = 9780521593458

| page = 8

| publisher = Cambridge University Press

| series = Cambridge Tracts in Mathematics

| title = Bipartite Graphs and their Applications

| volume = 131

| year = 1998}}

{{citation

| last = Rédei | first = László | author-link = László Rédei

| journal = Acta Litteraria Szeged

| pages = 39–43

| title = Ein kombinatorischer Satz

| volume = 7

| year = 1934}}

{{citation

| last = Roy | first = B.

| doi = 10.1051/m2an/1967010501291 | doi-access = free

| issue = 5

| journal = Rev. Française Informat. Recherche Opérationnelle

| language = French

| mr = 0225683

| pages = 129–132

| title = Nombre chromatique et plus longs chemins d'un graphe

| url = http://archive.numdam.org/ARCHIVE/M2AN/M2AN_1967__1_5/M2AN_1967__1_5_129_0/M2AN_1967__1_5_129_0.pdf

| volume = 1

| year = 1967}}

{{citation

| last = Sridharan | first = S.

| doi = 10.1016/0012-365X(93)90341-P

| issue = 1-3

| journal = Discrete Mathematics

| mr = 1226148

| pages = 265–270

| title = On the strong path partition conjecture of Berge

| volume = 117

| year = 1993}}; see p. 267, "an orientation of an odd cycle always contains a path of length 2"

{{citation

| last = Витавер | first = Л. М.

| journal = Doklady Akademii Nauk SSSR

| language = Russian

| mr = 0145509

| pages = 758–759

| title = Нахождение минимальных раскрасок вершин графа с помощью булевых степеней матрицы смежностей [Determination of minimal coloring of vertices of a graph by means of Boolean powers of the incidence matrix]

| volume = 147

| year = 1962}}

}}

{{DEFAULTSORT:Gallai-Hasse-Roy-Vitaver theorem}}

Category:Graph coloring

Category:Theorems in graph theory

Category:Duality theories