Logo
All Random Solved Random Open
OPEN
Is there a graph of chromatic number $\aleph_1$ such that for all $\epsilon>0$ if $n$ is sufficiently large and $H$ is a subgraph on $n$ vertices then $H$ contains an independent set of size $>n^{1-\epsilon}$?
Conjectured by Erdős, Hajnal, and Szemerédi [EHS82].