Erdős–Hajnal conjecture for hereditary graph classes

A graph $H$ is an induced subgraph of a graph $G$ if $H$ can be obtained from $G$ by removing vertices. A class of graphs is hereditary if it is closed under taking induced subgraphs and under isomorphism, and it is proper if it is not the class of all graphs. A hereditary class has the Erdős–Hajnal property if there exists $c>0$ such that every $n$-vertex graph in the class contains a clique or a stable set of size at least $n^c$.

Erdős–Hajnal conjecture. Every proper hereditary class of graphs has the Erdős–Hajnal property.

Equivalently, for every fixed graph $H$, the class of graphs with no induced copy of $H$ should contain a clique or stable set of polynomial size in the number of vertices. The conjecture is a strengthening of Ramsey's theorem; the paper notes that it has been proved for graphs of bounded VC-dimension, while the general assertion remains open.