OPEN
This is open, and cannot be resolved with a finite computation.
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.
View the LaTeX source
When referring to this problem, please use the original sources of Erdős. If you wish to acknowledge this website, the recommended citation format is:
T. F. Bloom, Erdős Problem #61, https://www.erdosproblems.com/61, accessed 2026-01-16
