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.

The stronger odd-minor variant known as the odd Hadwiger conjecture has been disproved (Kühn et al. 2025).

Kriesell and Mohr (2022) studied a rooted-minor problem involving Kempe chains whose affirmative answer would imply the Hadwiger conjecture for uniquely optimally colorable graphs, proving a special case and giving limitations on related sufficient conditions.