Induced subgraphs of graphs with large chromatic number. II. Three steps towards Gyárfás' conjectures

Maria Chudnovsky; Alex Scott; Paul Seymour

doi:10.1016/j.jctb.2016.01.003

Induced subgraphs of graphs with large chromatic number. II. Three steps towards Gyárfás' conjectures

Maria Chudnovsky, Alex Scott, Paul Seymour

Mathematics

Research output: Contribution to journal › Article › peer-review

12 Scopus citations

Abstract

Gyárfás conjectured in 1985 that for all k, ℓ, every graph with no clique of size more than k and no odd hole of length more than ℓ has chromatic number bounded by a function of k, ℓ. We prove three weaker statements:. •Every triangle-free graph with sufficiently large chromatic number has an odd hole of length different from five;•For all ℓ, every triangle-free graph with sufficiently large chromatic number contains either a 5-hole or an odd hole of length more than ℓ•For all k, ℓ, every graph with no clique of size more than k and sufficiently large chromatic number contains either a 5-hole or a hole of length more than ℓ.

Original language	English (US)
Pages (from-to)	109-128
Number of pages	20
Journal	Journal of Combinatorial Theory. Series B
Volume	118
DOIs	https://doi.org/10.1016/j.jctb.2016.01.003
State	Published - May 1 2016

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Keywords

Colouring
Holes
Induced subgraph
χ-Bounded

Access to Document

10.1016/j.jctb.2016.01.003

Cite this

@article{ed73e8dbdf9947858fe7fc0c16cce29e,

title = "Induced subgraphs of graphs with large chromatic number. II. Three steps towards Gy{\'a}rf{\'a}s' conjectures",

abstract = "Gy{\'a}rf{\'a}s conjectured in 1985 that for all k, ℓ, every graph with no clique of size more than k and no odd hole of length more than ℓ has chromatic number bounded by a function of k, ℓ. We prove three weaker statements:. •Every triangle-free graph with sufficiently large chromatic number has an odd hole of length different from five;•For all ℓ, every triangle-free graph with sufficiently large chromatic number contains either a 5-hole or an odd hole of length more than ℓ•For all k, ℓ, every graph with no clique of size more than k and sufficiently large chromatic number contains either a 5-hole or a hole of length more than ℓ.",

keywords = "Colouring, Holes, Induced subgraph, χ-Bounded",

author = "Maria Chudnovsky and Alex Scott and Paul Seymour",

note = "Publisher Copyright: {\textcopyright} 2016 Elsevier Inc.",

year = "2016",

month = may,

day = "1",

doi = "10.1016/j.jctb.2016.01.003",

language = "English (US)",

volume = "118",

pages = "109--128",

journal = "Journal of Combinatorial Theory. Series B",

issn = "0095-8956",

publisher = "Academic Press Inc.",

}

TY - JOUR

T1 - Induced subgraphs of graphs with large chromatic number. II. Three steps towards Gyárfás' conjectures

AU - Chudnovsky, Maria

AU - Scott, Alex

AU - Seymour, Paul

PY - 2016/5/1

Y1 - 2016/5/1

N2 - Gyárfás conjectured in 1985 that for all k, ℓ, every graph with no clique of size more than k and no odd hole of length more than ℓ has chromatic number bounded by a function of k, ℓ. We prove three weaker statements:. •Every triangle-free graph with sufficiently large chromatic number has an odd hole of length different from five;•For all ℓ, every triangle-free graph with sufficiently large chromatic number contains either a 5-hole or an odd hole of length more than ℓ•For all k, ℓ, every graph with no clique of size more than k and sufficiently large chromatic number contains either a 5-hole or a hole of length more than ℓ.

AB - Gyárfás conjectured in 1985 that for all k, ℓ, every graph with no clique of size more than k and no odd hole of length more than ℓ has chromatic number bounded by a function of k, ℓ. We prove three weaker statements:. •Every triangle-free graph with sufficiently large chromatic number has an odd hole of length different from five;•For all ℓ, every triangle-free graph with sufficiently large chromatic number contains either a 5-hole or an odd hole of length more than ℓ•For all k, ℓ, every graph with no clique of size more than k and sufficiently large chromatic number contains either a 5-hole or a hole of length more than ℓ.

KW - Colouring

KW - Holes

KW - Induced subgraph

KW - χ-Bounded

UR - http://www.scopus.com/inward/record.url?scp=84961216266&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84961216266&partnerID=8YFLogxK

U2 - 10.1016/j.jctb.2016.01.003

DO - 10.1016/j.jctb.2016.01.003

M3 - Article

AN - SCOPUS:84961216266

SN - 0095-8956

VL - 118

SP - 109

EP - 128

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

ER -

Induced subgraphs of graphs with large chromatic number. II. Three steps towards Gyárfás' conjectures

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this