  A well-known theorem of R\"odl says that for every graph $H$, and every
$\epsilon>0$, there exists $\delta>0$ such that if $G$ does not contain an
induced copy of $H$, then there exists $X\subseteq V(G)$ with $|X|\ge\delta|G|$
such that one of $G[X],\overline{G}[X]$ has edge-density at most $\epsilon$.
But how does $\delta$ depend on $\epsilon$? Fox and Sudakov conjectured that
the dependence can be taken to be polynomial: for all $H$ there exists $c>0$
such that for all $\epsilon\in(0,1/2)$, R\"odl's theorem holds with
$\delta=\epsilon^c$. This conjecture implies the Erd\H{o}s-Hajnal conjecture,
and until now it had not been verified for any non-trivial graphs $H$. Our
first result shows that it is true when $H=P_4$ (indeed, we can take
$\delta=\epsilon$, and insist that one of $G[X],\overline{G}[X]$ has maximum
degree at most $\epsilon^2|G|$).)
  We will generalize this, and to do so, we need to work with an even stronger
property. Let us say $H$ is {\em viral} if there exists $c>0$ such that for all
$\epsilon\in(0,1/2)$, if $G$ contains at most $\epsilon^c|G|^{|H|}$ induced
copies of $H$, then there exists $X\subseteq V(G)$ with $|X|\ge \epsilon^c|G|$
such that one of $G[X],\overline{G}[X]$ has density at most $\epsilon$. We will
show that $P_4$ is viral, using a ``polynomial $P_4$-removal lemma'' of Alon
and Fox. We will also show that viral graphs are closed under
vertex-substitution, and so all graphs that can be obtained by substitution
from copies of $P_4$ are viral. (In a subsequent paper, it will be shown that
all graphs currently known to satisfy the Erd\H{o}s-Hajnal conjecture are in
fact viral.)
  Finally, we give a different strengthening of R\"odl's theorem: we show that
if $G$ does not contain an induced copy of $P_4$, then its vertices can be
partitioned into at most $480\epsilon^{-4}$ subsets $X$ such that one of
$G[X],\overline{G}[X]$ has density at most $\epsilon$.
