[Math] Generalizations of the four-color theorem

big-listco.combinatoricsgraph theorygraph-colorings

The four color theorem asserts that every planar graph can be properly colored by four colors.

The purpose of this question is to collect generalizations, variations, and strengthenings of the four color theorem with a description of their status.

(Motivated by a comment of rupeixu to a recent blog post on my blog presenting a question by Abby Thompson regarding a natural generalization of the 4CT.)
Related question:Generalizations of Planar Graphs .

Best Answer

One of the most important generalizations of the four color theorem is Hadwiger's conjecture. The Hadwiger conjecture asserts that a graph without a $K_{r+1}$ minor is $r$-colorable. There is a further generalization called the Weak Hadwiger Conjecture.

It is known that the Hadwiger conjecture is false for graphs with infinite chromatic number (consider the disjoint union of $K_n$ where $n\in\mathbb{N}$), whereas the Weak Hadwiger conjecture is true for those graphs (see this paper).

An interesting question is whether the Weak Hadwiger conjecture implies the Hadwiger conjecture for finite graphs.