IBM - Personal communication

This web page contains the abstract of my paper:

"A Note on the Independence Number of Triangle-free Graphs II", RC 13344, Journal of Combinatorial Theory Series B, 53(1991), p. 300-307.

Abstract: Let G be a triangle-free graph on n points with degree sequence d1,...,dn. Let a be the independence number of G. Let f(0)=1, f(d) = [1+(d*d-d)*f(d-1)]/(d*d+1) for d >= 1. We prove a >= {sum over i from 1 to n of f(di)}. We also show slightly stronger results as the girth of G tends to infinity.

[ IBM Research home page | James B. Shearer's home page | Up ]
[ IBM home page | Order | Search | Contact IBM | Help | (C) | (TM) ]