Largest bipartite subgraph of a triangle free graph

A problem on bipartite subgraphs of triangle-free graphs[2]

Let \(f(m)\) denote that largest integer \(t\) so that a triangle-free graph on \(m\) edges always contains a bipartite graph of \(f(m)\) edges. Determine \(f(m)\).

Erdös and Lovász[2] proved that

\(\displaystyle f(m) \geq \frac 1 2 m + c m^{2/3} (\frac {\log m }{\log \log m})^{1/3}. \)

This was improved by Poljak and Tuza [3] to a lower bound of

\(\displaystyle f(m) \geq m/2 + c (m \log m)^{2/3}.\)

This was further improved by Shearer [4] to

\(\displaystyle f(m) \geq \frac 1 2 m + c m^{3/4}. \)

In 1996, Alon[1] proved that

\(\displaystyle \frac 1 2 m + c m^{4/5} \leq f(m) \leq \frac 1 2 m + c' m^{4/5}. \)

1 N. Alon. Bipartite subgraphs. Combinatorica 16 (1996), 301-311.

2 F. R. K. Chung, P. Erdös and R. L. Graham, On the product of the point and line covering numbers of a graph, Second International Conference on Combinatorial Mathematics (New York, 1978), Ann. N. Y. Acad. Sci. 319, 597-602, New York Acad. Sci., New York, 1979.

3 S. Poljak and Z. Tuza. Bipartite subgraphs of triangle-free graphs. SIAM J. Discrete Math. 7 (1994), 307-313.

4 J. B. Shearer, A note on bipartite subgraphs of triangle-free graphs, Random Structures and Algorithms 3 (1992), 223-226.