Improper colouring of graphs with no odd clique minor

Abstract

As a strengthening of Hadwigers 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 (3) 2, every graph with no odd Kt minor has a partition of its vertex set into 6t - 9 sets V-1, ..., V6t-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,..., V10t -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.