Making a triangle-free graph bipartite

There are many problems on triangles and triangle-free graphs in the problem paper [1]. The following problem was proposed in 1988.

A problem on making a triangle-free graph bipartite (proposed by Erdös, Faudree, Pach and Spencer [3])

Is it true that every triangle-free graph on \(5n\) vertices can be made bipartite by deleting at most \(n^2\) edges?

This conjecture, if true, would be best possible, as can be seen by considering the construction of a \( 5\)-partite graph with vertex sets \( S_i\), \( i = 1, \ldots, 5\), on \( n\) vertices each, and putting complete bipartite graphs between \( S_i\) and \( S_{i+1}\) where the index addition is taken modulo \( 5\).

Erdös, Györi and Simonovits [2] proved this conjecture for graphs with at least \( 5n^2\) edges. However, the general conjecture is still open for graphs with \( e\) edges for \( 2n^2 < e \leq 5 n^2\).

1 P. Erdös, Some problems on finite and infinite graphs, Logic and combinatorics (Arcata, Calif., 1985), Contemp. Math. 65, 223-228, Amer. Math. Soc., Providence, R. I., 1987.

2 P. Erdös, E. Györi and M. Simonovits, How many edges should be deleted to make a triangle-free graph bipartite?, Sets, graphs and numbers (Budapest, 1991), Colloq. Math. Soc. János Bolyai, 60, 239-263, North-Holland, Amsterdam, 1992.

3 P. Erdös, R. Faudree, J. Pach and J. H. Spencer, How to make a graph bipartite, J. Comb. Theory Ser. B 45 (1988), 86-98.