Author
Chudnovsky, M
Fox, J
Scott, A
Seymour, P
Spirkl, S
Journal title
Combinatorica
DOI
10.1007/s00493-019-3957-8
Issue
5
Volume
39
Last updated
2024-04-01T10:01:33.047+01:00
Page
983-991
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) .
Symplectic ID
944799
Favourite
Off
Publication type
Journal Article
Publication date
02 Oct 2019
Please contact us with feedback and comments about this page. Created on 21 Nov 2018 - 08:11.