IBM - Personal communication

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) ]