Journal article icon

Journal article

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á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.
Publication status:
Published
Peer review status:
Peer reviewed

Actions


Access Document


Files:
Publisher copy:
10.1016/j.jctb.2015.10.002

Authors


More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Mathematical Institute
Role:
Author
Publisher:
Elsevier
Journal:
Journal of Combinatorial Theory, Series B More from this journal
Volume:
121
Pages:
68–84
Publication date:
2015-10-30
DOI:
ISSN:
0095-8956
Keywords:
Pubs id:
pubs:632956
UUID:
uuid:abdeb96f-58c7-4774-8ded-cb6fba701e2b
Local pid:
pubs:632956
Source identifiers:
632956
Deposit date:
2016-07-09

Terms of use


Views and Downloads






If you are the owner of this record, you can report an update to it here: Report update to this record

TO TOP