Largest bipartite subgraph of a triangle free graph
Home
Search
Subjects
About Erdös
About This Site
Search
Subjects
 All (170)
 Ramsey Theory (40)
 Extremal Graph Theory (40)
 Coloring, Packing, and Covering (25)
 Random Graphs and Graph Enumeration (16)
 Hypergraphs (35)
 Infinite Graphs (14)
About Erdös
About This Site
A problem on bipartite subgraphs of trianglefree graphs[2]
Let \(f(m)\) denote that largest integer \(t\) so that a trianglefree 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}. \)
Bibliography  

1  N. Alon. Bipartite subgraphs. Combinatorica 16 (1996), 301311.

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,
597602, New York Acad. Sci., New York, 1979.

3  S. Poljak and Z. Tuza. Bipartite subgraphs of trianglefree graphs. SIAM J. Discrete Math. 7 (1994), 307313.

4  J. B. Shearer, A note on bipartite subgraphs of trianglefree graphs, Random Structures and Algorithms 3
(1992), 223226.
