For most graphs H, most H-free graphs have a linear homogeneous set
Erdos and Hajnal conjectured that for every graph H there is a constant ε =ε (H) > 0 such that every graph G that does not have H as an induced subgraph contains a clique or a stable set of order Ω(|V (G)|ε). The conjecture would be false if we set ε = 1; however, in an asymptotic setting, we...
| Main Authors: | , , , |
|---|---|
| Format: | Journal article |
| Published: |
Wiley
2013
|
| Summary: | Erdos and Hajnal conjectured that for every graph H there is a constant ε =ε (H) > 0 such that every graph G that does not have H as an induced subgraph contains a clique or a stable set of order Ω(|V (G)|ε). The conjecture would be false if we set ε = 1; however, in an asymptotic setting, we obtain this strengthened form of Erdos and Hajnal's conjecture for almost every graph H, and in particular for a large class of graphs H defined by variants of the colouring number. |
|---|