Problem Statement
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?
Categories:
Graph Theory
Progress
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.Source: erdosproblems.com/61 | Last verified: January 13, 2026