On the independence number of sparse graphs

Abstract

Abstract Let G be a regular graph of degree d on n points which contains no K r ( r ≥ 4). Let α be the independence number of G . Then we show for large d that α ≥ c(r)n . © 1995 John Wiley & Sons, Inc.