Naga Ayachitula, Melissa Buco, et al.
SCC 2007
Paper
A note on bipartite subgraphs of triangle‐free graphs
Abstract
Let G be a triangle‐free graph on n points with m edges and vertex degrees d1, d2,…, dn. Let k be the maximum number of edges in a bipartite subgraph of G. In this note we show that k ⩾ m/2 + Σ ni=1 √di. It follows as a corollary that k ⩾ m/2 + cm3/4. Copyright © 1992 Wiley Periodicals, Inc., A Wiley Company