Hadwiger Conjecture

The Hadwiger conjecture is a generalization of the four-color theorem which states that for any loopless graph with Hadwiger number and chromatic number ,

(Hadwiger 1943).

The case 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 by Robertson et al. (1993). However, while the validity of the conjecture has been established for all graphs with , it remains open for larger values.