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 α(G)α(G) of a graph GG is at least ∑u∈V(G)1dG(u)+1. In the present paper we conjecture the stronger bound α(G)≥∑u∈V(G)2dG(u)+ωG(u)+1 where ωG(u)ωG(u) is the maximum order of a clique of GG that contains the vertex uu. 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.