Towards Erdős-Hajnal for graphs with no 5-hole
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 Hajn...
| Main Authors: | , , , , |
|---|---|
| Format: | Journal article |
| Language: | English |
| Published: |
Springer Berlin Heidelberg
2019
|