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.