2 October 2019
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) .
Submitted to ORA: