  Erd\H{o}s and Hajnal conjectured that for every graph $H$, there exists $c>0$
such that every $H$-free graph $G$ has a clique or a stable set of size at
least $|G|^c$ (a graph is $H$-free if it has no induced subgraph isomorphic to
$H$). Alon, Pach, and Solymosi reduced the Erd\H{o}s-Hajnal conjecture to the
case when $H$ is {\em prime} (that is, $H$ cannot be obtained by
vertex-substitution from smaller graphs); but until now, it was not shown for
any prime graph with more than five vertices.
  We will provide infinitely many prime graphs that satisfy the conjecture. Let
$H$ be a graph with the property that for every prime induced subgraph $G'$
with $|G'|\ge 3$, $G'$ has a vertex of degree one and a vertex of degree
$|G'|-2$. We will prove that every graph $H$ with this property satisfies the
Erd\H{o}s-Hajnal conjecture, and infinitely many graphs with this property are
prime. More generally, say a graph is {\em buildable} if every prime induced
subgraph with at least three vertices has a vertex of degree one. We prove that
if $H_1$ and $\overline{H_2}$ are buildable, there exists $c>0$ such that every
graph $G$ that is both $H_1$-free and $H_2$-free has a clique or a stable set
of size at least $|G|^c$.
  Our proof uses a new technique of ``iterative sparsification'', where we pass
to a sequence of successively more restricted induced subgraphs. This approach
also extends to ordered graphs and to tournaments. For ordered graphs, we
obtain a theorem which significantly extends a recent result of Pach and Tomon
about excluding monotone paths; and for tournaments, we obtain infinitely many
new prime tournaments that satisfy the Erd\H{o}s-Hajnal conjecture (in
tournament form).
