Problem 75

Erdős Problem #75: declared status 'open'. Formalized: yes. 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}$? Prize: no. Tags: chromatic number, graph theory.