SOLVED
Let $k\geq 0$. Let $G$ be a graph such that every subgraph $H$ contains an independent set of size $\geq (n-k)/2$, where $n$ is the number of vertices of $H$. Must $G$ have chromatic number at most $k+2$?
A question of Erdős and Hajnal
[ErHa67b]. The case $k=0$ is trivial, but they could not prove this even for $k=1$.
This is true, and was proved by Folkman [Fo70b].
See also [73].
