On Selkow's Bound on the Independence Number of Graphs

Abstract

For a graph $G$ with vertex set $V(G)$ and independence number $\alpha (G)$, S. M. Selkow (Discrete Mathematics, 132(1994)363--365) established the famous lower bound $\sum _{v\in V(G)}\frac{1}{d(v)+1}(1+\max \{\frac{d(v)}{d(v)+1}-\sum _{u\in N(v)}\frac{1}{d(u)+1},0\})$ on $\alpha (G)$, where $N(v)$ and $d(v)=|N(v)|$ denote the neighborhood and the degree of a vertex $v\in V(G)$, respectively. However, Selkow's original proof of this result is incorrect. We give a new probabilistic proof of Selkow's bound here.

Cited by in corpus (3)

• Fractional coloring with local demands and applications to degree-sequence bounds on the independence number
• Improving the Caro-Wei bound and applications to Turán stability
• On the extremal graphs for degenerate subsets, dynamic monopolies, and partial incentives