The Erdös-Hajnal Conjecture---A Survey

Abstract

The Erdös-Hajnal conjecture states that for every graph $H$, there exists a constant $\delta (H)>0$ such that every graph $G$ with no induced subgraph isomorphic to $H$ has either a clique or a stable set of size at least $|V(G){|}^{\delta (H)}$. This paper is a survey of some of the known results on this conjecture.