Improper colouring of graphs with no odd clique minor
Dong Yeap Kang, Sang-Il Oum · Combinatorics Probability Computing · 2019
Abstract As a strengthening of Hadwiger’s conjecture, Gerards and Seymour conjectured that every graph with no odd K t 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 K t minor has a partition of its vertex set into 6 t − 9 sets V 1 , …, V 6 t −9 such that each V i 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 10 t −13 sets V 1 ,…, V 10 t −13 such that each V i 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 496 t such sets.