Loading...
Please wait, while we are loading the content...
Similar Documents
Improper colouring of graphs with no odd clique minor
| Content Provider | Scilit |
|---|---|
| Author | Kang, Dong Yeap Oum, Sang-Il |
| Copyright Year | 2019 |
| Description | As a strengthening of Hadwiger’s conjecture, Gerards and Seymour conjectured that every graph with no $oddK_{t}$minor is (t− 1)-colourable. We prove two weaker variants of this conjecture. Firstly, we show that for eacht⩾ 2, every graph with no $oddK_{t}$minor has a partition of its vertex set into 6t− 9 $setsV_{1}$, $…,V_{6}_{t}_{−9}$such that $eachV_{i}$induces a subgraph of bounded maximum degree. Secondly, we prove that for eacht⩾ 2, every graph with no odd Kt minor has a partition of its vertex set into 10t−13 $setsV_{1},…,V_{10}_{t}_{−13}$such that $eachV_{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 496tsuch sets. |
| Related Links | http://arxiv.org/pdf/1612.05372 https://www.cambridge.org/core/services/aop-cambridge-core/content/view/F0C6091DDB46096417FFDAF60FCEC87C/S0963548318000548a.pdf/div-class-title-improper-colouring-of-graphs-with-no-odd-clique-minor-div.pdf |
| Ending Page | 754 |
| Page Count | 15 |
| Starting Page | 740 |
| ISSN | 09635483 |
| e-ISSN | 14692163 |
| DOI | 10.1017/s0963548318000548 |
| Journal | Combinatorics, Probability and Computing |
| Issue Number | 5 |
| Volume Number | 28 |
| Language | English |
| Publisher | Cambridge University Press (CUP) |
| Publisher Date | 2019-09-01 |
| Access Restriction | Open |
| Subject Keyword | Combinatorics, Probability and Computing Applied Mathematics Primary 05c15 Secondary 05c83 |
| Content Type | Text |
| Resource Type | Article |
| Subject | Applied Mathematics Statistics and Probability Theoretical Computer Science Computational Theory and Mathematics |
