For most graphs H, most H‐free graphs have a linear homogeneous set1. Issue 3 (18th March 2013) - Kang, Ross J.
ABSTRACT Erdős 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 Erdős 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. © 2013 Wiley Periodicals, Inc. Random Struct. Alg., 45, 343–361, 2014