Improper coloring 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 $K_t$ minor is $(t-1)$-colorable. We prove two weaker variants of this conjecture. Firstly, we show that for each $t\ge 2$, every graph with no odd $K_t$ minor has a partition of its vertex set into $6t-9$ sets $V_1,\dots ,V_{6t-9}$ such that each $V_i$ induces a subgraph of bounded maximum degree. Secondly, we prove that for each $t\ge 2$, every graph with no odd $K_t$ minor has a partition of its vertex set into $10t-13$ sets $V_1,\dots ,V_{10t-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 $496t$ such sets.

15 pages

References in corpus (4)

• Improper Colourings inspired by Hadwiger's Conjecture
• A relative of Hadwiger's conjecture
• Defective colouring of graphs excluding a subgraph or minor
• Partitioning $H$-minor free graphs into three subgraphs with no large components

Cited by in corpus (5)

• Improper Colourings inspired by Hadwiger's Conjecture
• Clustered 3-Colouring Graphs of Bounded Degree
• Clustered Variants of Hajós' Conjecture
• Clustered Coloring of Graphs with Bounded Layered Treewidth and Bounded Degree
• Colouring Strong Products