Improperly coloring K_t minor-free graphs

Improperly coloring K_t minor-free graphs

-
Sergey Norin , McGill University
Fine Hall 224

We show that for every t > 0 there exists a constant c=c(t) such that, if a graph G does not contain K_t as a minor, then its vertex set can be partitioned into at most t-1 parts such that every part induces a subgraph with maximum component of size at most c. This relaxation of Hadwiger's conjecture improves previous results of Kawarabayashi and Mohar, Wood, and Liu and Oum, who proved that the same conclusion holds for partitions into 31t/2, 7t/2 and 3t parts respectively.  We also discuss applications of our results to extremal questions on bootstrap percolation for minor-closed graph families. Based on joint work with Zdenek Dvorak.