The Hadwiger conjecture is a generalization of the four-color theorem which states that for any loopless graph G with h(G) the Hadwiger number and χ(G) the chromatic number, h(G)>=χ(G) (Hadwiger 1943). The case k = 5 is equivalent to the four-color theorem, so the proof of the latter proves the conjecture for this case. The conjecture was proven for h(G) = 6 by Robertson et al. (1993). While the validity of the conjecture has been established for all h(G)<=6, it remains open for larger values.

chromatic number | four-color theorem | Hadwiger-Nelson problem | Hadwiger number