Originators: P. Erdős and A. Hajnal (presented by J. Cooper - REGS 2009)
Definitions: The homogeneous number of a graph G, denoted hom(G), is the maximum of the clique number and the independence number. A graph is H-free if it does not have H as an induced subgraph.
Conjecture: (Erdős-Hajnal [EH]) For every graph H, there is a nonzero constant ε such that when G is an H-free graph with n vertices, hom(G)∈Ω(nε).
Comments: By the familiar counting argument of Erdős, there exist graphs G such that hom(G) ≤ 2 lg n. Forbidding a fixed induced subgraph gives a chance of forcing a larger homogeneous set. As a general lower bound, results from Ramsey theory yield hom(G) ≥ e c(H)√log n, but this is not a polynomial lower bound. When the statement holds for H, let &epsilon(H) = sup{ε: hom(G)∈&Omega(nε)}.
Actually, [EH] merely "asks" whether the statement is true. It holds for all graphs with at most four vertices. Results on the Ramsey numbers R(3,k) yield ε(K3)=1/2. It is known that ε(H)=1/3 when H is the claw K1,3 or the claw plus one edge (the paw). Also 1/3<ε(C4)≤3/7 (see [G]) and ε(K4-)>1/3.
All graphs for which the conjecture is known to be true are perfect, but it is not known to be true for all perfect graphs. Does it hold when H=C5? [APS] showed that the family of all H for which the conjecture holds is closed under lexicographic composition, as is the family of perfect graphs. To prove the conjecture for a graph H, we need only consider graphs G that are not perfect, since hom(G)≥n1/2 when G is perfect.
References:
[APS] Alon, N.; Pach, J.; Solymosi, J.;
Ramsey-type theorems with forbidden subgraphs.
Paul Erdős and his mathematics (Budapest, 1999).
Combinatorica 21 (2001), no. 2, 155--170.
[EH] Erdős P.; Hajnal, A.
Ramsey-type theorems.
Combinatorics and complexity (Chicago, IL, 1987).
Discrete Appl. Math. 25 (1989), no. 1-2, 37--52.
[G] Gyárfás, András Reflections on a problem of Erdős
and Hajnal. The Mathematics of Paul Erdős, II, 93--98, Algorithms
Combin., 14, Springer, Berlin, 1997