Induced Subgraphs of Graphs with Large Chromatic Number. III. Long Holes

Maria Chudnovsky; Alex Scott; Paul Seymour

doi:10.1007/s00493-016-3467-x

Induced Subgraphs of Graphs with Large Chromatic Number. III. Long Holes

Mathematics

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

29 Scopus citations

Abstract

We prove a 1985 conjecture of Gyárfás that for all k, ℓ, every graph with sufficiently large chromatic number contains either a clique of cardinality more than k or an induced cycle of length more than ℓ.

Original language	English (US)
Pages (from-to)	1057-1072
Number of pages	16
Journal	Combinatorica
Volume	37
Issue number	6
DOIs	https://doi.org/10.1007/s00493-016-3467-x
State	Published - Dec 1 2017

All Science Journal Classification (ASJC) codes

Discrete Mathematics and Combinatorics
Computational Mathematics

Access to Document

10.1007/s00493-016-3467-x

Cite this

@article{33125934e75b457ba3c495f98f0d10d8,

title = "Induced Subgraphs of Graphs with Large Chromatic Number. III. Long Holes",

abstract = "We prove a 1985 conjecture of Gy{\'a}rf{\'a}s that for all k, ℓ, every graph with sufficiently large chromatic number contains either a clique of cardinality more than k or an induced cycle of length more than ℓ.",

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

note = "Publisher Copyright: {\textcopyright} 2016, J{\'a}nos Bolyai Mathematical Society and Springer-Verlag Berlin Heidelberg.",

year = "2017",

month = dec,

day = "1",

doi = "10.1007/s00493-016-3467-x",

language = "English (US)",

volume = "37",

pages = "1057--1072",

journal = "Combinatorica",

issn = "0209-9683",

publisher = "Janos Bolyai Mathematical Society",

number = "6",

}

TY - JOUR

T1 - Induced Subgraphs of Graphs with Large Chromatic Number. III. Long Holes

AU - Chudnovsky, Maria

AU - Scott, Alex

AU - Seymour, Paul

PY - 2017/12/1

Y1 - 2017/12/1

N2 - We prove a 1985 conjecture of Gyárfás that for all k, ℓ, every graph with sufficiently large chromatic number contains either a clique of cardinality more than k or an induced cycle of length more than ℓ.

AB - We prove a 1985 conjecture of Gyárfás that for all k, ℓ, every graph with sufficiently large chromatic number contains either a clique of cardinality more than k or an induced cycle of length more than ℓ.

UR - https://www.scopus.com/pages/publications/84997684109

UR - https://www.scopus.com/pages/publications/84997684109#tab=citedBy

U2 - 10.1007/s00493-016-3467-x

DO - 10.1007/s00493-016-3467-x

M3 - Article

AN - SCOPUS:84997684109

SN - 0209-9683

VL - 37

SP - 1057

EP - 1072

JO - Combinatorica

JF - Combinatorica

IS - 6

ER -

Induced Subgraphs of Graphs with Large Chromatic Number. III. Long Holes

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this