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

Author: 

Chudnovsky, M
Fox, J
Scott, A
Seymour, P
Spirkl, S

Publication Date: 

2 October 2019

Journal: 

Combinatorica

Last Updated: 

2020-01-31T06:20:14.157+00:00

Issue: 

5

Volume: 

39

DOI: 

10.1007/s00493-019-3957-8

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

Submitted to ORA: 

Submitted

Publication Type: 

Journal Article