Improper colouring of graphs with no odd clique minor
DC Field | Value | Language |
---|---|---|
dc.contributor.author | Kang D.Y. | - |
dc.contributor.author | Sang-Il Oum | - |
dc.date.available | 2019-11-13T07:32:18Z | - |
dc.date.created | 2019-03-12 | - |
dc.date.issued | 2019-09 | - |
dc.identifier.issn | 0963-5483 | - |
dc.identifier.uri | https://pr.ibs.re.kr/handle/8788114/6423 | - |
dc.description.abstract | As a strengthening of Hadwiger's conjecture, Gerards and Seymour conjectured that every graph with no odd Kt minor is (t - 1)-colourable. We prove two weaker variants of this conjecture. Firstly, we show that for each t 2, every graph with no odd Kt minor has a partition of its vertex set into 6t - 9 sets V 1, V 6 t -9 such that each Vi induces a subgraph of bounded maximum degree. Secondly, we prove that for each t 2, every graph with no odd Kt minor has a partition of its vertex set into 10t -13 sets V 1, V 10 t -13 such that each Vi 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. © 2019 Cambridge University Press | - |
dc.description.uri | 1 | - |
dc.language | 영어 | - |
dc.publisher | CAMBRIDGE UNIV PRESS | - |
dc.title | Improper colouring of graphs with no odd clique minor | - |
dc.type | Article | - |
dc.type.rims | ART | - |
dc.identifier.wosid | 000500255000006 | - |
dc.identifier.scopusid | 2-s2.0-85061090125 | - |
dc.identifier.rimsid | 67049 | - |
dc.contributor.affiliatedAuthor | Sang-Il Oum | - |
dc.identifier.doi | 10.1017/S0963548318000548 | - |
dc.identifier.bibliographicCitation | COMBINATORICS PROBABILITY & COMPUTING, v.28, no.5, pp.740 - 754 | - |
dc.citation.title | COMBINATORICS PROBABILITY & COMPUTING | - |
dc.citation.volume | 28 | - |
dc.citation.number | 5 | - |
dc.citation.startPage | 740 | - |
dc.citation.endPage | 754 | - |
dc.description.journalClass | 1 | - |
dc.description.isOpenAccess | N | - |
dc.description.journalRegisteredClass | scie | - |
dc.description.journalRegisteredClass | scopus | - |
dc.subject.keywordPlus | EXTREMAL FUNCTION | - |
dc.subject.keywordPlus | CONJECTURE | - |