Almost-bipartite graphs with infinite chromatic number

A problem on graphs of infinite chromatic number ($250): (proposed by Erdös, Hajnal and Szemerédi, 1982) [1]

Let \(f(n) \rightarrow \infty\) arbitrarily slowly. Is it true that there is a graph \(G\) of infinite chromatic number such that for every \(n\), every subgraph of \(G\) of \(n\) vertices can be made bipartite by deleting at most \(f(n)\) edges?

Prove or disprove the existence of a graph \(G\) of infinite chromatic number for which \(f(n)= o(n^{\epsilon})\) or \(f(n)= o((\log n)^c)\).

Rödl [2] solved this problem for 3-graphs, showing that there always is such a \( G\).

Bibliography
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.

2 V. Rödl, Nearly bipartite graphs with large chromatic number, Combinatorica 2 (1982), 377-383.