Erdős-Hajnal conjecture beyond five-vertex graphs

Shenwei Huang, Yiao Ju, Yidong Zhou

In 1989, Erdős and Hajnal conjectured 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…