Problem Statement
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}$?
Categories:
Graph Theory Chromatic Number
Progress
Conjectured by Erdős, Hajnal, and Szemerédi [EHS82]. In [Er95d] Erdős suggests this may even be true with an independent set of size $\gg n$.See also [750].
Source: erdosproblems.com/75 | Last verified: January 13, 2026