A lower bound on the independence number of a graph in terms of degrees and local clique sizes

Caro and Wei independently showed that the independence number alpha(G) of a graph G is at least Sigma(u is an element of V(G)) 1/d(G)(u)+1. In the present paper we conjecture the stronger bound alpha(G) >= Sigma(u is an element of V(G)) 2/d(G)(u)+omega(G)(u)+1 where omega(G)(u) is the maximum order of a clique of G that contains the vertex u. We discuss the relation of our conjecture to recent conjectures and results concerning the independence number and the chromatic number. Furthermore, we prove our conjecture for perfect graphs and for graphs of maximum degree at most 4. (C) 2015 Elsevier B.V. All rights reserved.