Publication
Journal of Combinatorial Theory, Series B
Paper

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

View publication

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.

Date

Publication

Journal of Combinatorial Theory, Series B

Authors

Share