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

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