Hadwiger conjecture (graph theory)

In graph theory, the Hadwiger conjecture (or "Hadwiger's conjecture") states that, if the complete graph on <math>k<math> vertices, <math>K_k<math>, is not a minor of a graph <math>G<math>, then <math>G<math> has a vertex coloring with <math>k-1<math> colors. Equivalently, if there is no sequence of edge contractions (each identifying the two endpoints of an edge) that brings graph <math>G<math> to the complete graph <math>K_k<math>, then <math>G<math> has a vertex coloring with <math>k-1<math> colors.

This conjecture was made by Hugo Hadwiger in 1943. In the same paper, Hadwiger proved the conjecture for <math>k \leq 4<math>. Wagner proved in 1937 that the case <math>k=5<math> is equivalent to the four color theorem and therefore we now know it to be true. (Note that the case <math>k=5<math> easily implies the four color theorem because <math>K_5<math> is not a minor of any planar graph.) Robertson, Seymour, and Thomas (1993) proved Hadwiger's conjecture for <math>k=6<math>, also using the four color theorem. Thus the conjecture is true for <math>k \leq 6<math> but it remains unsolved for all <math>k > 6<math>.

Hadwiger number

Some sources define the Hadwiger number <math>h(G)<math> of a graph <math>G<math> to be the size <math>k<math> of the largest complete graph <math>K_k<math> that is a minor of <math>G<math> (or equivalently can be obtained by contracting <math>G<math>). Then the Hadwiger conjecture can be stated in the simple algebraic form <math>\chi(G) \leq h(G)<math> where <math>\chi(G)<math> denotes the chromatic number of <math>G<math>.

References

• Hadwiger, H. (1943). "Über eine Klassifikation der Streckenkomplexe" (German). Vierteljschr. Naturforsch. ges. Zürich 88, 133–143.

• Robertson, Neil; Seymour, Paul; Thomas, Robin (1993). "Hadwiger's conjecture for <math>K_6<math>-free graphs". Combinatorica 14, 279–361.