The Erd\H{o}s--Hajnal property for paths

Abstract

The well-known Erd\H{o}s-Hajnal conjecture states that for any graph $H$, there is a constant $c=c(H)>0$ such that every $n$-vertex graph $G$ with no induced copies of $H$ contains a clique or an independent set of size at least $n^{c}$. In this paper, we prove that the Erd\H{o}s-Hajnal conjecture holds for every path.