Journal article icon

Journal article

Induced subgraphs of graphs with large chromatic number. III. Long holes

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 ℓ.
Publication status:
Published
Peer review status:
Peer reviewed
Version:
Accepted Manuscript

Actions


Access Document


Files:
Publisher copy:
10.1007/s00493-016-3467-x

Authors


More by this author
Institution:
University of Oxford
Department:
Oxford, MPLS, Mathematical Institute
Role:
Author
Publisher:
Springer Berlin Heidelberg Publisher's website
Journal:
Combinatorica Journal website
Volume:
37
Issue:
6
Pages:
1057–1072
Publication date:
2016-11-28
Acceptance date:
2016-03-22
DOI:
EISSN:
1439-6912
ISSN:
0209-9683
URN:
uuid:da0b21cb-00bf-4ef8-8298-fc3cf9b35170
Source identifiers:
632957
Local pid:
pubs:632957
Keywords:

Terms of use


Metrics


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