A note on the independence number of triangle-free graphs, II

Abstract

Let G be a triangle-free graph on n points with degree sequence d1, ..., dn. Let α be the independence number of G. Let f(0) = 1, f(d) = [1 + (d2 - d) f(d - 1)] (d2 + 1)d ≥ 1. We prove α ≥ Σi = 1n f(di). We also show slightly stronger results as the girth of G tends to ∞. © 1991.