A New Lower Bound on the Independence Number of Graphs✩
Éric Angel, Romain Campigotto, Christian Laforest · 2015
We propose a new lower bound on the independence number of a graph. We show that our bound compares favorably to recent ones (e.g. [12]). We obtain our bound by using the Bhatia-Davis inequality applied with analytical results (minimum, maximum, expectation and variance) of an algorithm for the vertex cover problem.