Discrete Math Seminar

Hadwiger famously conjectured that every $K_h$-minor-free graph is properly $(h-1)$-colourable. This talk will present the following improper analogue of Hadwiger's Conjecture: for fixed $h$, every $K_h$-minor-free graph is $(h-1)$-colourable with monochromatic components of bounded size. The number of colours is best possible regardless of the size of monochromatic components. This solves an open problem of …