Induced subgraphs of graphs with large chromatic number. VIII. Long odd holes

Maria Chudnovsky; Alex Scott; Paul Seymour; Sophie Spirkl

doi:10.1016/j.jctb.2019.05.001

Induced subgraphs of graphs with large chromatic number. VIII. Long odd holes

Maria Chudnovsky, Alex Scott, Paul Seymour, Sophie Spirkl

Mathematics

Princeton University

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

4 Scopus citations

Abstract

We prove a conjecture of András Gyárfás, that for all κ,ℓ, every graph with clique number at most κ and sufficiently large chromatic number has an odd hole of length at least ℓ.

Original language	American English
Pages (from-to)	84-97
Number of pages	14
Journal	Journal of Combinatorial Theory. Series B
Volume	140
DOIs	https://doi.org/10.1016/j.jctb.2019.05.001
State	Published - Jan 2020

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Access to Document

10.1016/j.jctb.2019.05.001

Cite this

@article{b5d58ce9d247413da84b030706e8052e,

title = "Induced subgraphs of graphs with large chromatic number. VIII. Long odd holes",

abstract = "We prove a conjecture of Andr{\'a}s Gy{\'a}rf{\'a}s, that for all κ,ℓ, every graph with clique number at most κ and sufficiently large chromatic number has an odd hole of length at least ℓ.",

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

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

year = "2020",

month = jan,

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

language = "American English",

volume = "140",

pages = "84--97",

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. VIII. Long odd holes

AU - Chudnovsky, Maria

AU - Scott, Alex

AU - Seymour, Paul

AU - Spirkl, Sophie

PY - 2020/1

Y1 - 2020/1

N2 - We prove a conjecture of András Gyárfás, that for all κ,ℓ, every graph with clique number at most κ and sufficiently large chromatic number has an odd hole of length at least ℓ.

AB - We prove a conjecture of András Gyárfás, that for all κ,ℓ, every graph with clique number at most κ and sufficiently large chromatic number has an odd hole of length at least ℓ.

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

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

U2 - 10.1016/j.jctb.2019.05.001

DO - 10.1016/j.jctb.2019.05.001

M3 - Article

SN - 0095-8956

VL - 140

SP - 84

EP - 97

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

ER -

Induced subgraphs of graphs with large chromatic number. VIII. Long odd holes

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this