pith. sign in

arxiv: 1612.05372 · v3 · pith:Z3FVF2KHnew · submitted 2016-12-16 · 🧮 math.CO

Improper coloring of graphs with no odd clique minor

classification 🧮 math.CO
keywords minoreverygraphsetsvertexboundedconjecturedots
0
0 comments X
read the original 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 \geq 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 \geq 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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.