On Rödl's Theorem for Cographs

Abstract

A theorem of Rödl states that for every fixed $F$ and $\epsilon >0$ there is $\delta ={\delta }_F(\epsilon )$ so that every induced $F$-free graph contains a vertex set of size $\delta n$ whose edge density is either at most $\epsilon$ or at least $1-\epsilon$. Rödl's proof relied on the regularity lemma, hence it supplied only a tower-type bound for $\delta$. Fox and Sudakov conjectured that $\delta$ can be made polynomial in $\epsilon$, and a recent result of Fox, Nguyen, Scott and Seymour shows that this conjecture holds when $F=P_4$. In fact, they show that the same conclusion holds even if $G$ contains few copies of $P_4$. In this note we give a short proof of a more general statement.