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

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

Hadwiger number

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

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 K₆-free graphs". Combinatorica 14, 279-361.