Induced subgraphs of graphs with large chromatic number. I. Odd holes

Alex Scott; Paul Seymour

doi:10.1016/j.jctb.2015.10.002

Induced subgraphs of graphs with large chromatic number. I. Odd holes

Alex Scott, Paul Seymour

Mathematics

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

49 Scopus citations

Abstract

An odd hole in a graph is an induced subgraph which is a cycle of odd length at least five. In 1985, A. Gyárfás made the conjecture that for all t there exists n such that every graph with no K_t subgraph and no odd hole is n-colourable. We prove this conjecture.

Original language	English (US)
Pages (from-to)	68-84
Number of pages	17
Journal	Journal of Combinatorial Theory. Series B
Volume	121
DOIs	https://doi.org/10.1016/j.jctb.2015.10.002
State	Published - Nov 1 2016

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Keywords

Colouring
Induced subgraphs
Odd holes

Access to Document

10.1016/j.jctb.2015.10.002

Cite this

@article{16fc7c62a05d43a3926cd47c1d4e6cbb,

title = "Induced subgraphs of graphs with large chromatic number. I. Odd holes",

abstract = "An odd hole in a graph is an induced subgraph which is a cycle of odd length at least five. In 1985, A. Gy{\'a}rf{\'a}s made the conjecture that for all t there exists n such that every graph with no Kt subgraph and no odd hole is n-colourable. We prove this conjecture.",

keywords = "Colouring, Induced subgraphs, Odd holes",

author = "Alex Scott and Paul Seymour",

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

year = "2016",

month = nov,

day = "1",

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

language = "English (US)",

volume = "121",

pages = "68--84",

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. I. Odd holes

AU - Scott, Alex

AU - Seymour, Paul

PY - 2016/11/1

Y1 - 2016/11/1

N2 - An odd hole in a graph is an induced subgraph which is a cycle of odd length at least five. In 1985, A. Gyárfás made the conjecture that for all t there exists n such that every graph with no Kt subgraph and no odd hole is n-colourable. We prove this conjecture.

AB - An odd hole in a graph is an induced subgraph which is a cycle of odd length at least five. In 1985, A. Gyárfás made the conjecture that for all t there exists n such that every graph with no Kt subgraph and no odd hole is n-colourable. We prove this conjecture.

KW - Colouring

KW - Induced subgraphs

KW - Odd holes

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

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

U2 - 10.1016/j.jctb.2015.10.002

DO - 10.1016/j.jctb.2015.10.002

M3 - Article

AN - SCOPUS:84991726486

SN - 0095-8956

VL - 121

SP - 68

EP - 84

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

ER -

Induced subgraphs of graphs with large chromatic number. I. Odd holes

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this