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
|