Bipartite Subgraphs of Triangle-Free Graphs
Svatopluk Poljak, Źsolt Tuza · SIAM Journal on Discrete Mathematics · 1994
The authors present a lower bound on the maximum size of a bipartite subgraph of a triangle-free graph that improves a result due to Erdös and Lovász. It also gives a polynomial-time algorithm, while the previous bound was proved by probabilistic methods.