Improper coloring of graphs with no odd clique minor
arXiv:1612.05372 · doi:10.1017/S0963548318000548
Abstract
As a strengthening of Hadwiger's conjecture, Gerards and Seymour conjectured that every graph with no odd minor is -colorable. We prove two weaker variants of this conjecture. Firstly, we show that for each , every graph with no odd minor has a partition of its vertex set into sets such that each induces a subgraph of bounded maximum degree. Secondly, we prove that for each , every graph with no odd minor has a partition of its vertex set into sets such that each 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 such sets.
arXiv comment15 pages
References in corpus (7)
- Improper Colourings inspired by Hadwiger's Conjecture
- A relative of Hadwiger's conjecture
- Defective colouring of graphs excluding a subgraph or minor
- Coloring planar graphs with three colors and no large monochromatic components
- Partitioning -minor free graphs into three subgraphs with no large components
- Even-cycle decompositions of graphs with no odd--minor
- Improper choosability and Property B