Every graph with chromatic number t contains the complete graph K_t as a
minor. A graph minor may be obtained by deleting vertices, deleting edges, and
contracting edges.
The conjecture unifies graph colouring and graph structure. It would extend
the four-colour theorem: the case t=5 is closely tied to planar graphs.
The conjecture is proved for small chromatic numbers, including the cases up
to t=6; the general case is open.
High chromatic number is a global colouring obstruction, while producing a specific complete minor requires a compatible collection of connected branch sets.
Learn graph minors, prove that a K_t minor forces suitable chromatic
behaviour, and work through why the four-colour theorem implies the t=5
case.
To exhibit a K_t minor, produce t pairwise disjoint connected branch sets
with at least one edge between every pair of branch sets. This formulation is
often more useful than performing contractions one at a time.
For a claimed minor, list every branch set, prove it is connected, prove the
sets are disjoint, and exhibit an edge for each of the t choose 2 pairs.
For a colouring argument, distinguish subgraphs from minors: they behave very
differently under contraction.
Study Wagner's theorem, the Robertson--Seymour graph-minor theorem, and the
connections among planarity, K_5, and K_{3,3}.