Improper colouring of graphs with no odd clique minor

Abstract

As a strengthening of Hadwiger's conjecture, Gerards and Seymour conjectured that every graph with no odd Kt minor is (t - 1)-colourable. We prove two weaker variants of this conjecture. Firstly, we show that for each t 2, every graph with no odd Kt minor has a partition of its vertex set into 6t - 9 sets V 1, V 6 t -9 such that each Vi induces a subgraph of bounded maximum degree. Secondly, we prove that for each t 2, every graph with no odd Kt minor has a partition of its vertex set into 10t -13 sets V 1, V 10 t -13 such that each Vi induces a subgraph with components of bounded size. The second theorem improves a result of Kawarabayashi (2008), which states that the vertex set can be partitioned into 496t such sets. © 2019 Cambridge University Press