Improper colouring of graphs with no odd clique minor
| Autor: | Dong Yeap Kang, Sang-il Oum |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
Statistics and Probability
Vertex (graph theory) Mathematics::Combinatorics Conjecture Applied Mathematics 010102 general mathematics 0102 computer and information sciences 01 natural sciences Graph Theoretical Computer Science Combinatorics Computational Theory and Mathematics Computer Science::Discrete Mathematics 010201 computation theory & mathematics Bounded function FOS: Mathematics Mathematics - Combinatorics Partition (number theory) 05C15 05C83 Combinatorics (math.CO) 0101 mathematics Mathematics |
| Zdroj: | Combinatorics, Probability and Computing. 28:740-754 |
| ISSN: | 1469-2163 0963-5483 |
| DOI: | 10.1017/s0963548318000548 |
| Popis: | 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. 15 pages |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|