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.