Is it true that $f_k(n)\to \infty$ as $n\to \infty$? In particular, is it true that $f_4(n) \gg \log n$?

SOLVED

Let $k$ be a large fixed constant. Let $f_k(n)$ be the minimal $m$ such that there exists a graph $G$ on $n$ vertices with chromatic number $k$, such that every proper subgraph has chromatic number $<k$, and $G$ can be made bipartite by deleting $m$ edges.

Is it true that $f_k(n)\to \infty$ as $n\to \infty$? In particular, is it true that $f_4(n) \gg \log n$?

A problem of Erdős, Hajnal, and Szemerédi [EHS82]. Odd cycles show that $f_3(n)=1$, but they expected $f_4(n)\to \infty$. Gallai [Ga68] gave a construction which shows
\[f_4(n) \ll n^{1/2},\]
and Lovász extended this to show
\[f_k(n) \ll n^{1-\frac{1}{k-2}}.\]

This conjecture was disproved by Rödl and Tuza [RoTu85], who proved that in fact $f_k(n)=\binom{k-1}{2}$ (for all sufficiently large $n$).