Authors: J. Harant, S. Mohr Title: On Selkow's bound on the independence number of graphs Source: Discussiones Mathematicae Graph Theory Received 20.11.2017, Revised 20.11.2017, Accepted 18.12.2017, doi: 10.7151/dmgt.2100 Abstract: For a graph G with vertex set V(G) and independence number α(G), Selkow [ A Probabilistic lower bound on the independence number of graphs, Discrete Math. 132 (1994) 363--365] established the famous lower bound ∑v∈V(G)\frac{1}{d(v)+1}\bigg(1+\max\bigg{\frac{d(v)}{d(v)+1}-∑u∈N(v)\frac{1}{d(u)+1},0 \bigg}\bigg) on α(G), where N(v) and d(v)=|N(v)| denote the neighborhood and the degree of a vertex v∈V(G), respectively. However, Selkow's original proof of this result is incorrect. We give a new probabilistic proof of Selkow's bound here. Keywords: graph, independence number Links: PDF