Problem 61

Erdős Problem #61: declared status 'open'. Formalized: yes. 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? Prize: no. Tags: graph theory.