In graph theory, the Hadwiger conjecture (or "Hadwiger's conjecture") states that, if the complete graph on k vertices, Kk, 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 Kk, 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 K5 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 Kk 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.