Journal article icon

Journal article

Induced subgraphs of graphs with large chromatic number. II. Three steps towards Gyarfas' conjectures

Abstract:

Gyárfás conjectured in 1985 that for all k, ℓ, every graph with no clique of size more than k and no odd hole of length more than ℓ has chromatic number bounded by a function of k, ℓ. We prove three weaker statements:. •Every triangle-free graph with sufficiently large chromatic number has an odd hole of length different from five;•For all ℓ, every triangle-free graph with sufficiently large chromatic number contains either a 5-hole or an odd hole of length more than ℓ•For all k, ℓ, every gra...

Expand abstract
Publication status:
Published
Peer review status:
Peer reviewed
Version:
Accepted manuscript

Actions


Access Document


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

Authors


More by this author
Institution:
University of Oxford
Department:
Oxford, MPLS, Mathematical Institute
Role:
Author
Publisher:
Elsevier B.V. Publisher's website
Journal:
Journal of Combinatorial Theory, Series B Journal website
Volume:
118
Pages:
109-128
Chapter number:
C
Publication date:
2016-01-27
Acceptance date:
2015-08-28
DOI:
EISSN:
1096-0902
ISSN:
0095-8956
URN:
uuid:91edfafa-aecb-47da-a3fe-36b1d7d70f35
Source identifiers:
604679
Local pid:
pubs:604679

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