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 assertion that every -minor-free graph is 4-colorable is equivalent to the four-color theorem. Robertson et al. (1993) proved that every -minor-free graph is 5-colorable. Thus is established when .

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.