Any graph with many large independent sets is almost bipartite

A problem on almost bipartite graphs (proposed by Erdös [1])

Suppose \(G\) has the property that for every \(m\), every subgraph on \(m\) vertices contains an independent set of size \(m/2-k\). Let \(f(k)\) denote the smallest number such that \(G\) can be made bipartite by deleting \(f(k)\) vertices.
Determine \(f(k)\).

In the mid 1990s, Reed proved the existence of \( f(k)\) by using graph minors, but did not publish the result. It would be of interest to improve the estimates for \( f(k)\).

Erdös, Hajnal and Szemerédi [1] proved that for every \( \epsilon>0\), there is a graph of infinite chromatic number for which every subgraph of \( m\) vertices contains an independent set of size \( (1-\epsilon)m/2\). Erdös remarked that perhaps \( (1-\epsilon)m/2\) could be replaced by \( m/2-f(m)\) where \( f(m)\) tends to infinity arbitrarily slowly.

1 P. Erdös, A. Hajnal and E. Szemerédi, On almost bipartite large chromatic graphs, Annals of Discrete Math. 12 (1982), Theory and practice of combinatorics, North-Holland Math. Stud., 60, 117-123, North-Holland, Amsterdam, New York, 1982.