Séminaire

Hadwiger conjectured that every graph with no K_t minor is (t-1)-colorable , in other words, every graph with no K_t minor admits a partition of its vertex set into t-1 independent sets. This conjecture is still widely open and if true, it implies the four color theorem. Gerards and Seymour made a stronger conjecture claiming that every graph with no K_t odd minor is (t-1)-colorable, commonly called the odd Hadwiger’s conjecture. We prove variants of Hadwiger’s conjecture. First, we prove that every graph with no K_t minor admits a partition of its vertex set into t-1 sets, each inducing a subgraph of bounded maximum degree. Secondly, we prove that every graph with no K_t minor admits a partition of its vertex set into 3(t-1) sets, each inducing a subgraph having no large components. We also prove variants of the odd Hadwiger’s conjecture as follows : Every graph with no odd K_t minor admits a partition of its vertex set into 7t-10 sets, each inducing a subgraph of bounded maximum degree. As a corollary, we prove that every graph with no odd K_t minor admits a partition of its vertex set into 28t-40 sets, each inducing a subgraph with no large components. The last result improves the result of Kawarabayashi, who showed it with 496t sets. This talk is a combination of three works , first with K. Edwards, D. Kang, J. Kim, and P. Seymour, second with C. Liu, and third with D. Kang.