Unsolved problem in mathematics:(more unsolved problems in mathematics) |

In graph theory, the **Hadwiger conjecture** states that if G is loopless and has no minor then its chromatic number satisfies . It is known to be true for . The conjecture is a generalization of the four-color theorem and is considered to be one of the most important and challenging open problems in the field.^{[1]}

In more detail, if all proper colorings of an undirected graph *G* use *k* or more colors, then one can find *k* disjoint connected subgraphs of *G* such that each subgraph is connected by an edge to each other subgraph. Contracting the edges within each of these subgraphs so that each subgraph collapses to a single vertex produces a complete graph *K _{k}* on

This conjecture, a far-reaching generalization of the four-color problem, was made by Hugo Hadwiger in 1943 and is still unsolved. Bollobás, Catlin & Erdős (1980) call it “one of the deepest unsolved problems in graph theory.”^{[2]}

An equivalent form of the Hadwiger conjecture (the contrapositive of the form stated above) is that, if there is no sequence of edge contractions (each merging the two endpoints of some edge into a single supervertex) that brings a graph *G* to the complete graph *K _{k}*, then

Note that, in a minimal *k*-coloring of any graph *G*, contracting each color class of the coloring to a single vertex will produce a complete graph *K _{k}*. However, this contraction process does not produce a minor of

If *F _{k}* denotes the family of graphs having the property that all minors of graphs in

The Hadwiger number *h*(*G*) of a graph *G* is the size *k* of the largest complete graph *K _{k}* that is a minor of

The case *k* = 2 is trivial: a graph requires more than one color if and only if it has an edge, and that edge is itself a *K*_{2} minor. The case *k* = 3 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 *K*_{3} minor.

In the same paper in which he introduced the conjecture, Hadwiger proved its truth for *k* ≤ 4. The graphs with no *K*_{4} 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 *k* = 5 implies the four color theorem: for, if the conjecture is true, every graph requiring five or more colors would have a *K*_{5} minor and would (by Wagner's theorem) be nonplanar.
Klaus Wagner proved in 1937 that the case *k* = 5 is actually equivalent to the four color theorem and therefore we now know it to be true. As Wagner showed, every graph that has no *K*_{5} minor can be decomposed via clique-sums into pieces that are either planar or an 8-vertex Möbius ladder, and each of these pieces can be 4-colored independently of each other, so the 4-colorability of a *K*_{5}-minor-free graph follows from the 4-colorability of each of the planar pieces.

Robertson, Seymour & Thomas (1993) proved the conjecture for *k* = 6, 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 *k* ≤ 6, but it remains unsolved for all *k* > 6.

For *k* = 7, some partial results are known: every 7-chromatic graph must contain either a *K*_{7} minor or both a *K*_{4,4} minor and a *K*_{3,5} minor.^{[4]}

Every graph *G* has a vertex with at most O(*h*(*G*) √log *h*(*G*)) 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 O(*h*(*G*) √log *h*(*G*)) colors.

Van der Zypen (2012) has constructed a graph *H* with *χ(H) = ω* but no *K _{ω}* minor, demonstrating that the conjecture does

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 *k* contains a subdivision of a complete graph *K _{k}*. Hajós' conjecture is true for

Borowiecki (1993) asked whether Hadwiger's conjecture could be extended to list coloring. For *k* ≤ 4, every graph with list chromatic number *k* has a *k*-vertex clique minor. However, the maximum list chromatic number of planar graphs is 5, not 4, so the extension fails already for *K*_{5}-minor-free graphs.^{[7]} More generally, for every *t* ≥ 1, there exist graphs whose Hadwiger number is 3*t* + 1 and whose list chromatic number is 4*t* + 1.^{[8]}

Gerards and Seymour conjectured that every graph *G* with chromatic number *k* has a complete graph *K _{k}* as an

By imposing extra conditions on *G*, it may be possible to prove the existence of larger minors than *K _{k}*. 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.

**^**Diestel, Reinhard, 1959- Verfasser. (30 June 2017).*Graph theory*. ISBN 9783662536216. OCLC 1048203362.CS1 maint: multiple names: authors list (link)- ^
^{a}^{b}^{c}Bollobás, Catlin & Erdős (1980). **^**Nešetřil & Thomas (1985).**^**The existence of either a*K*_{7}or*K*_{3,5}minor was shown by Ken-ichi Kawarabayashi, and Kawarabayashi & Toft (2005) proved the existence of either a*K*_{7}or*K*_{4,4}minor.**^**Kostochka (1984). The letter O in this expression invokes big O notation.**^**Yu & Zickfeld (2006).**^**Voigt (1993); Thomassen (1994).**^**Barát, Joret & Wood (2011).**^**Geelen et al. (2006); Kawarabayashi (Journal of Combinatorial Theory, Series B, Volume 99, Issue 1, January 2009, Pages 20-29).**^**Pegg, Ed, Jr. (2002), "Book Review: The Colossal Book of Mathematics" (PDF),*Notices of the American Mathematical Society*,**49**(9): 1084–1086, Bibcode:2002ITED...49.1084A, doi:10.1109/TED.2002.1003756.

- Barát, János; Joret, Gwenaël; Wood, David R. (2011), "Disproof of the list Hadwiger conjecture",
*Electronic Journal of Combinatorics*,**18**(1): P232, arXiv:1110.2272. - Bollobás, B.; Catlin, P. A.; Erdős, Paul (1980), "Hadwiger's conjecture is true for almost every graph" (PDF),
*European Journal of Combinatorics*,**1**(3): 195–199, doi:10.1016/s0195-6698(80)80001-1. - Borowiecki, Mieczyslaw (1993), "Research problem 172",
*Discrete Mathematics*,**121**(1–3): 235–236, doi:10.1016/0012-365X(93)90557-A. - Catlin, P. A. (1979), "Hajós's graph-colouring conjecture: variations and counterexamples",
*Journal of Combinatorial Theory, Series B*,**26**(2): 268–274, doi:10.1016/0095-8956(79)90062-5. - Erdős, Paul; Fajtlowicz, Siemion (1981), "On the conjecture of Hajós",
*Combinatorica*,**1**(2): 141–143, doi:10.1007/BF02579269. - Geelen, Jim; Gerards, Bert; Reed, Bruce; Seymour, Paul; Vetta, Adrian (2006), "On the odd-minor variant of Hadwiger's conjecture",
*Journal of Combinatorial Theory, Series B*,**99**(1): 20–29, doi:10.1016/j.jctb.2008.03.006. - Hadwiger, Hugo (1943), "Über eine Klassifikation der Streckenkomplexe",
*Vierteljschr. Naturforsch. Ges. Zürich*,**88**: 133–143. - Kawarabayashi, Ken-ichi,
*Minors in 7-chromatic graphs*, Preprint. - Kawarabayashi, Ken-ichi (2009), "Note on coloring graphs without odd
*K*-minors",_{k}*Journal of Combinatorial Theory, Series B*,**99**(4): 728, doi:10.1016/j.jctb.2008.12.001.*Journal of Combinatorial Theory, Series B*, in press. - Kawarabayashi, Ken-ichi; Toft, Bjarne (2005), "Any 7-chromatic graph has
*K*_{7}or*K*_{4,4}as a minor",*Combinatorica*,**25**(3): 327–353, doi:10.1007/s00493-005-0019-1. - Kostochka, A. V. (1984), "Lower bound of the Hadwiger number of graphs by their average degree",
*Combinatorica*,**4**(4): 307–316, doi:10.1007/BF02579141. - Nešetřil, Jaroslav; Thomas, Robin (1985), "A note on spatial representation of graphs",
*Commentationes Mathematicae Universitatis Carolinae*,**26**(4): 655–659, archived from the original on 2011-07-18, retrieved 2010-08-06. - Robertson, Neil; Seymour, Paul; Thomas, Robin (1993), "Hadwiger's conjecture for K
_{6}-free graphs" (PDF),*Combinatorica*,**13**(3): 279–361, doi:10.1007/BF01202354. - Thomassen, Carsten (1994), "Every planar graph is 5-choosable",
*Journal of Combinatorial Theory*, Series B,**62**(1): 180–181, doi:10.1006/jctb.1994.1062, MR 1290638. - Van der Zypen, Dominic (2012),
*Hadwiger's conjecture for graphs with infinite chromatic number*, arXiv:1212.3093, Bibcode:2012arXiv1212.3093V. - Voigt, Margit (1993), "List colourings of planar graphs",
*Discrete Mathematics*,**120**(1–3): 215–219, doi:10.1016/0012-365X(93)90579-I, MR 1235909. - Wagner, Klaus (1937), "Über eine Eigenschaft der ebenen Komplexe",
*Mathematische Annalen*,**114**: 570–590, doi:10.1007/BF01594196. - 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, doi:10.1016/j.jctb.2005.10.001.