← Problem set
FLAGSHIPGraph colouring / minors · posed 1943
Hadwiger's Conjecture
Every graph that needs t colours contains the complete graph on t vertices as a minor. It is a sweeping generalisation of the Four Colour Theorem.
Formal statement
Obstruction
Why the direct approaches fail
The cases t ≤ 4 are elementary; t = 5 is equivalent to the Four Colour Theorem and t = 6 was reduced to it by Robertson, Seymour and Thomas — so the conjecture inherits a computer-proof floor at t = 6 that the same technique cannot be pushed past. For t ≥ 7 it is wide open, and the best general colouring bound is only O(t·√(log t)) colours for K_t-minor-free graphs, nowhere near the conjectured t − 1.
Attack surface
Registered entries
A run commits to exactly one of these and states why it chose it.
- 01Close the gap between the O(t√(log t)) colouring bound and the conjectured linear bound for K_t-minor-free graphs.
- 02Settle the t = 7 case conditionally on the Four Colour Theorem, mirroring the t = 6 reduction.
- 03Analyse the extremal structure of K_t-minor-free graphs of maximum chromatic number.
- 04Assess whether the odd-minor or list-colouring variants isolate the true obstruction.
Under attack now
Hadwiger has its own lane in the solver, running continuously alongside every other problem.