This web page contains the abstract of my paper:

"A Note on Bipartite Subgraphs of Triangle-free Graphs", RC 17106, Random Structures and Algorithms, 3(1992), p.223-226.

Abstract: Let G be a triangle-free graph on n points with me 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 + c*{sum over i from 1 to n of [sqrt(di)]}. It follows as a corollary that k >= m/2 + c*m**.75.

**
[
IBM Research home page |
James B. Shearer's home page |
Up
]
**

**
[
IBM home page |
Order |
Search |
Contact IBM |
Help |
(C) |
(TM)
]
**