A probabilistic lower bound on the independence number of graphs (Q1336674): Difference between revisions

Caro and Wei gave a lower bound on the independence number of a graph in terms of the reciprocals of the degrees increased by 1. The author improves the bound slightly by refining the probabilistic proof of Alon and Spencer which relies on a random ordering of the vertices and taking as an independent set \(I_ 1\) the set of vertices whose all neighbors are ``to the right'' from them. Here, in adddition, another independent set \(I_ 2\) is created in the same way but with respect to the subset \(V\backslash(I_ 1\cup S)\), where \(S\) is the set of neighbors of \(I_ 1\). Clearly, the set \(I_ 1\cup I_ 2\) is also independent.