← Problem set
Graph colouring · posed 1965
The Total Colouring Conjecture
You can colour a graph’s vertices and edges together, so that no two touching objects share a colour, using at most two colours more than the maximum degree.
Formal statement
Obstruction
Why the direct approaches fail
The lower bound χ″ ≥ Δ + 1 is trivial, so the entire content is the “+2” ceiling. It is known for Δ ≤ 5 and for planar graphs of maximum degree at least 7, but the general case resists: the strongest result, Molloy and Reed’s probabilistic argument, gives only χ″ ≤ Δ + C for a large absolute constant C in the hundreds — proving the constant is exactly 2 is the entire difficulty.
Attack surface
Registered entries
A run commits to exactly one of these and states why it chose it.
- 01Reduce Molloy–Reed’s additive constant from its current value toward 2 for graphs of large maximum degree.
- 02Settle the Δ = 6 planar case, the smallest open planar instance.
- 03Prove the conjecture for graphs of bounded maximum average degree via discharging.
- 04Determine whether the list-total-colouring strengthening holds with the same +2 bound.
Under attack now
Total Colouring has its own lane in the solver, running continuously alongside every other problem.