Journal article icon

Journal article

Towards Erdős-Hajnal for graphs with no 5-hole

Abstract:
The Erdős-Hajnal conjecture says that for every graph H there exists c > 0 such that max(α(G), ω(G)) ≥ n c for every H-free graph G with n vertices, and this is still open when H = C5. Until now the best bound known on max(α(G), ω(G)) for C5-free graphs was the general bound of Erdős and Hajnal, that for all H, max(α(G), ω(G)) ≥ 2 Ω(√ log n) if G is H-free. We improve this when H = C5 to max(α(G), ω(G)) ≥ 2 Ω(√ log n log log n) .
Publication status:
Published
Peer review status:
Peer reviewed

Actions


Access Document


Files:
Publisher copy:
10.1007/s00493-019-3957-8

Authors


More by this author
Institution:
University of Oxford
Division:
MPLS
Department:
Mathematical Institute
Oxford college:
Merton College
Role:
Author
ORCID:
0000-0003-4489-5988
More from this funder
Funding agency for:
Scott, A
Grant:
Research Fellowship RF-2017-093\9
Publisher:
Springer Berlin Heidelberg Publisher's website
Journal:
Combinatorica Journal website
Volume:
39
Issue:
5
Pages:
983–991
Publication date:
2019-10-02
Acceptance date:
2018-11-20
DOI:
EISSN:
1439-6912
ISSN:
0209-9683
Source identifiers:
944799
Language:
English
Pubs id:
pubs:944799
UUID:
uuid:3961bf73-b689-4b8b-ac26-4140619978af
Local pid:
pubs:944799
Deposit date:
2018-11-21

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