OPEN
Let $f(m)$ be some function such that $f(m)\to \infty$ as $m\to \infty$. Does there exist a graph $G$ of infinite chromatic number such that every subgraph on $m$ vertices contains an independent set of size at least $\frac{m}{2}-f(m)$?
In
[Er69b] Erdős conjectures this for $f(m)=\epsilon m$ for any fixed $\epsilon>0$. In
[Er94b] he claims this weaker conjecture was proved by himself and Hajnal, but gives no reference.
In [ErHa67b] Erdős and Hajnal prove this for $f(m)\geq cm$ for all $c>1/4$.
See also [75].
