A graph without induced \(5\)-cycles has large cliques or independent sets

Problem [3]

Suppose \( G\) is a graph on \( n\) vertices containing no induced \( C_5\). Is it true that \( G\) must contain a clique or independent set of size \( n^{\epsilon}\)?
The same question was asked for any excluded subgraph -- \( C_5\) is the smallest graph where the answer is unknown. Erdös and Hajnal [3] showed that this conjecture is true when \( C_5\) is replaced by so-called ``very simple'' graphs. The very simple graphs are defined by containing the 1-vertex graph, and being closed under graph joins and disjoint unions.

In particular, if we replace \( C_5\) by \( C_4\), which is very simple, Gyárfás [4] showed that \( \epsilon\) is between \( 1/3\) and \( 3/7\).

Erdös and Hajnal [3] also noted that \( P_4\)-free graphs, being perfect, have cliques or independent sets of size \( n^{1/2}\). Likewise, the same holds for graphs containing neither induced odd cycles nor odd cycle complements of length at least 5, from the Strong Perfect Graph Theorem

Alon, Pach, and Solymosi [1] showed that, if \( G\) and \( H\) have the property that \( G\)-free and \( H\)-free graphs have cliques or independent sets of size \( n^{\epsilon}\), then so does any graph formed by replacing a vertex \( v\) of \( G\) with a copy of \( H\) (and connecting each vertex of \( H\) to the neighbors of \( v\) in \( G\)).

Chudnovsky and Safra showed that the bull graph also has this property.

Bibliography
1 N. Alon, J. Pach, and J. Solymosi, Ramsey-type theorems with forbidden subgraphs, Combinatorica 21 (2001), 155-170.

2 Maria Chudnovsky and Shmuel Safra. 2008. The Erdös-Hajnal conjecture for bull-free graphs. J. Comb. Theory Ser. B 98, 6 (November 2008), 1301-1310.

3 P. Erdös and A. Hajnal, Ramsey-type theorems, Combinatorics and complexity (Chicago, IL, 1987), Discrete Appl. Math. 25 (1989) no. 1-2, 37-52.

4 A. Gyárfás, Reflections on a problem of Erdös and Hajnal, The Mathematics of Paul Erdös, II (R. L. Graham and J. Nešetril, eds.), 93-98, Springer-Verlag, Berlin, 1996.