Mario Blaum, John L. Fan, et al.
IEEE International Symposium on Information Theory - Proceedings
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
Related
Zhihua Xiong, Yixin Xu, et al.
International Journal of Modelling, Identification and Control
Sonia Cafieri, Jon Lee, et al.
Journal of Global Optimization
Shashanka Ubaru, Lior Horesh, et al.
Journal of Biomedical Informatics