Lower bounds on the independence number of a graph in terms of degrees

Abstract

Given an integer $\Delta \ge 3$, let ${\mathcal{G}}_{\Delta }$ be the set of connected graphs $G\ne K_{\Delta +1}$ with maximum degree $\Delta$ and, for $i=1,\cdots ,\Delta$, let $V_i(G)$ be the set of vertices of $G$ of degree $i$. \\ We prove that $\sum _{i=1}^{\Delta }{c}_i|V_i(G)|$ is a lower bound on the independence number $\alpha (G)$ of $G\in {\mathcal{G}}_{\Delta }$, where $c_{\Delta }=\frac{1}{\Delta }$ and $i{c}_i=1-c_{i+1}$ for $i=1,\cdots ,\Delta -1$. Moreover, if $\epsilon >0$ and $j\in \{1,\cdots ,\Delta \}$, then the inequality $\alpha (G)\ge \epsilon |V_j(G)|+\sum _{i=1}^{\Delta }{c}_i|V_i(G)|$ does not hold for infinitely many graphs $G\in {\mathcal{G}}_{\Delta }$. We also show that an independent set $I\subset V(G)$ of $G\in {\mathcal{G}}_{\Delta }$ such that $|I|\ge \sum _{i=1}^{\Delta }{c}_i|V_i(G)|$ can be found in polynomial time.