OPEN
For any graph $H$ is there some $c=c(H)>0$ such that every graph $G$ on $n$ vertices that does not contain $H$ as an induced subgraph contains either a complete graph or independent set on $\geq n^c$ vertices?
Conjectured by Erdős and Hajnal
[ErHa89], who proved that a complete graph or independent set must exist on
\[\geq \exp(c_H\sqrt{\log n})\]
many vertices, where $c_H>0$ is some constant. This was improved by Bucić, Nguyen, Scott, and Seymour
[BNSS23] to
\[\geq \exp(c_H\sqrt{\log n\log\log n}).\]
See also the entry in the graphs problem collection.
