BROWSE

Related Scientist

Researcher

엄상일
수리 및 계산 과학 연구단
more info

Improper colouring of graphs with no odd clique minor

Cited 0 time in webofscience Cited 0 time in scopus
14 Viewed 2 Downloaded
Title
Improper colouring of graphs with no odd clique minor
Author(s)
Kang D.Y.; Sang-Il Oum
Publication Date
2019-09
Journal
COMBINATORICS PROBABILITY & COMPUTING, v.28, no.5, pp.740 - 754
Publisher
CAMBRIDGE UNIV PRESS
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
URI
https://pr.ibs.re.kr/handle/8788114/6423
ISSN
0963-5483
Appears in Collections:
Pioneer Research Center for Mathematical and Computational Sciences(수리 및 계산과학 연구단) > Discrete Mathematics Group(이산 수학 그룹) > Journal Papers (저널논문)
Files in This Item:
Improper colouring of graphs with no odd clique minor.pdfDownload

qrcode

  • facebook

    twitter

  • Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.
해당 아이템을 이메일로 공유하기 원하시면 인증을 거치시기 바랍니다.

Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.

Browse