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

Search

Subjects

- All (170)
- Ramsey Theory (40)
- Extremal Graph Theory (40)
- Coloring, Packing, and Covering (25)
- Random Graphs and Graph Enumeration (16)
- Hypergraphs (35)
- Infinite Graphs (14)

About Erdös

About This Site

# 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}\)?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.