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:
-
-
(Accepted manuscript, pdf, 207.7KB)
-
- Publisher copy:
- 10.1007/s00493-019-3957-8
Authors
Funding
+ Leverhulme Trust
More from this funder
Funding agency for:
Scott, A
Grant:
Research Fellowship RF-2017-093\9
Bibliographic Details
- 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
Item Description
- Language:
- English
- Pubs id:
-
pubs:944799
- UUID:
-
uuid:3961bf73-b689-4b8b-ac26-4140619978af
- Local pid:
- pubs:944799
- Source identifiers:
-
944799
- Deposit date:
- 2018-11-21
Terms of use
- Copyright holder:
- János Bolyai Mathematical Society and Springer-Verlag
- Copyright date:
- 2019
- Rights statement:
- Copyright © 2019 János Bolyai Mathematical Society and Springer-Verlag.
- Notes:
- This is the accepted manuscript version of the article. The final version is available online from Springer at http://dx.doi.org/10.1007/s00493-019-3957-8
Metrics
If you are the owner of this record, you can report an update to it here: Report update to this record