Hadwiger conjecture (graph theory)
Does every graph with
In graph theory, the Hadwiger conjecture states that if is loopless and has no
In more detail, if all
This conjecture, a far-reaching generalization of the
Equivalent forms
An equivalent form of the Hadwiger conjecture (the
In a minimal -coloring of any graph , contracting each color class of the coloring to a single vertex will produce a complete graph . However, this contraction process does not produce a minor of because there is (by definition) no edge between any two vertices in the same color class, thus the contraction is not an edge contraction (which is required for minors). Hadwiger's conjecture states that there exists a different way of properly edge contracting sets of vertices to single vertices, producing a complete graph , in such a way that all the contracted sets are connected.
If denotes the family of graphs having the property that all minors of graphs in can be -colored, then it follows from the Robertson–Seymour theorem that can be characterized by a finite set of forbidden minors. Hadwiger's conjecture is that this set consists of a single forbidden minor, .
The Hadwiger number of a graph is the size of the largest complete graph that is a minor of (or equivalently can be obtained by contracting edges of ). It is also known as the contraction clique number of .[2] The Hadwiger conjecture can be stated in the simple algebraic form where denotes the
Special cases and partial results
The case is trivial: a graph requires more than one color if and only if it has an edge, and that edge is itself a minor. The case is also easy: the graphs requiring three colors are the non-bipartite graphs, and every non-bipartite graph has an odd cycle, which can be contracted to a 3-cycle, that is, a minor.
In the same paper in which he introduced the conjecture, Hadwiger proved its truth for . The graphs with no minor are the series–parallel graphs and their subgraphs. Each graph of this type has a vertex with at most two incident edges; one can 3-color any such graph by removing one such vertex, coloring the remaining graph recursively, and then adding back and coloring the removed vertex. Because the removed vertex has at most two edges, one of the three colors will always be available to color it when the vertex is added back.
The truth of the conjecture for implies the four color theorem: for, if the conjecture is true, every graph requiring five or more colors would have a minor and would (by Wagner's theorem) be nonplanar.
Robertson, Seymour & Thomas (1993) proved the conjecture for , also using the four color theorem; their paper with this proof won the 1994 Fulkerson Prize. It follows from their proof that linklessly embeddable graphs, a three-dimensional analogue of planar graphs, have chromatic number at most five.[3] Due to this result, the conjecture is known to be true for , but it remains unsolved for all .
For , some partial results are known: every 7-chromatic graph must contain either a minor or both a minor and a minor.[4]
Every graph has a vertex with at most incident edges,[5] from which it follows that a greedy coloring algorithm that removes this low-degree vertex, colors the remaining graph, and then adds back the removed vertex and colors it, will color the given graph with colors.
In the 1980s, Alexander V. Kostochka[6] and Andrew Thomason[7] both independently proved that every graph with no minor has average degree and can thus be colored using colors. A sequence of improvements to this bound have led to a proof of -colorability for graphs without minors.[8]
Generalizations
György Hajós conjectured that Hadwiger's conjecture could be strengthened to subdivisions rather than minors: that is, that every graph with chromatic number contains a subdivision of a complete graph . Hajós' conjecture is true for , but Catlin (1979) found counterexamples to this strengthened conjecture for ; the cases and remain open.[9] Erdős & Fajtlowicz (1981) observed that Hajós' conjecture fails badly for random graphs: for any , in the limit as the number of vertices, , goes to infinity, the probability approaches one that a random -vertex graph has chromatic number , and that its largest clique subdivision has vertices. In this context, it is worth noting that the probability also approaches one that a random -vertex graph has Hadwiger number greater than or equal to its chromatic number, so the Hadwiger conjecture holds for random graphs with high probability; more precisely, the Hadwiger number is with high probability proportional to .[2]
Borowiecki (1993) asked whether Hadwiger's conjecture could be extended to list coloring. For , every graph with list chromatic number has a -vertex clique minor. However, the maximum list chromatic number of planar graphs is 5, not 4, so the extension fails already for -minor-free graphs.[10] More generally, for every , there exist graphs whose Hadwiger number is and whose list chromatic number is .[11]
Gerards and Seymour conjectured that every graph with chromatic number has a complete graph as an odd minor. Such a structure can be represented as a family of vertex-disjoint subtrees of , each of which is two-colored, such that each pair of subtrees is connected by a monochromatic edge. Although graphs with no odd minor are not necessarily
By imposing extra conditions on , it may be possible to prove the existence of larger minors than . One example is the snark theorem, that every cubic graph requiring four colors in any edge coloring has the Petersen graph as a minor, conjectured by W. T. Tutte and announced to be proved in 2001 by Robertson, Sanders, Seymour, and Thomas.[13]
Notes
- ^ Diestel (2017).
- ^ a b c Bollobás, Catlin & Erdős (1980).
- ^ Nešetřil & Thomas (1985).
- ^ The existence of either a or minor was shown by Ken-ichi Kawarabayashi, and Kawarabayashi & Toft (2005) proved the existence of either a or minor.
- ^ Kostochka (1984). The letter in this expression invokes big O notation.
- ^ Kostochka (1984).
- ^ Thomason (1984).
- ^ Delcourt & Postle (2021); Norin, Postle & Song (2023)
- ^ Yu & Zickfeld (2006).
- ^ Voigt (1993); Thomassen (1994).
- ^ Barát, Joret & Wood (2011).
- ^ Geelen et al. (2006); Kawarabayashi (2009).
- ^ Pegg (2002).
References
- Barát, János; Joret, Gwenaël; S2CID 13822279
- Borowiecki, Mieczyslaw (1993), "Research problem 172",
- Catlin, P. A. (1979), "Hajós's graph-colouring conjecture: variations and counterexamples", Journal of Combinatorial Theory, Series B, 26 (2): 268–274,
- Delcourt, Michelle; Postle, Luke (2021), Reducing linear Hadwiger's conjecture to coloring small graphs, arXiv:2108.01633
- Diestel, Reinhard (2017), "7.3 Hadwiger's conjecture", Graph Theory, Graduate Texts in Mathematics, vol. 173 (5th ed.), Springer, Berlin, pp. 183–186, MR 3822066
- S2CID 1266711
- Hadwiger, Hugo (1943), "Über eine Klassifikation der Streckenkomplexe", Vierteljschr. Naturforsch. Ges. Zürich, 88: 133–143
- MR 2518204
- S2CID 41451753
- Kostochka, A. V. (1984), "Lower bound of the Hadwiger number of graphs by their average degree", Combinatorica, 4 (4): 307–316, S2CID 15736799
- MR 0831801
- Norin, Sergey; Postle, Luke; Song, Zi-Xia (2023), "Breaking the degeneracy barrier for coloring graphs with no minor", MR 4576840
- Pegg, Ed Jr. (2002), "Book Review: The Colossal Book of Mathematics"(PDF), Notices of the American Mathematical Society, 49 (9): 1084–1086
- S2CID 9608738
- Thomason, Andrew (1984), "An extremal function for contractions of graphs", Mathematical Proceedings of the Cambridge Philosophical Society, 95 (2): 261–265, S2CID 124801301
- MR 1290638
- MR 1235909
- S2CID 123534907
- Yu, Xingxing; Zickfeld, Florian (2006), "Reducing Hajós' 4-coloring conjecture to 4-connected graphs", Journal of Combinatorial Theory, Series B, 96 (4): 482–492, MR 2232386