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$ be the union of a bipartite graph and $O_k(1)$ many vertices?
Proved by Reed
[Re99]. (Thanks also to Reed for pointing out that the case $k=0$ is trivial, since if $G$ is not bipartite then $G$ contains an odd cycle.)
See also [922] and the entry in the graphs problem collection.
