# 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.