Title: Proof of the Clustered Hadwiger Conjecture
| Speaker: | Vida Dujmovic |
| Affiliation: | University of Ottawa |
| Location: | MC 5501 |
Abstract: Hadwiger's Conjecture asserts that every Kh-minor-free graph is properly (h-1)-colourable. We prove the following improper analogue of Hadwiger's Conjecture: for fixed h, every Kh-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. It solves an open problem of Edwards, Kang, Kim, Oum and Seymour [SIAM J. Disc. Math. 2015], and concludes a line of research initiated in 2007. Similarly, for fixed t ⩾ s, we show that every Ks,t-minor-free graph is (s+1)-colourable with monochromatic components of bounded size. The number of colours is best possible, solving an open problem of van de Heuvel and Wood [J. London Math. Soc. 2018]. We actually prove a single theorem from which both of the above results are immediate corollaries.
This
is
joint
work
with
Louis
Esperet,
Pat
Morin
and
David
R.
Wood.