About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Random Structures and Algorithms
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