k‐Independence and the k‐residue of a graph
Frank Jelen · Journal of Graph Theory · 1999
Favaron et al. proved that the residue of a simple graph G is a lower bound on its independence number #alpha#(G). A vertex set X in a graph is called k-independent if the subgraph induced by X has maximum degree less than k. We prove that a generalization of the residue, the k-residue of a graph, yields a lower bound on the k-independence number. The new bound strengthens a bound of Caro and Tuza and improves all known bounds for some graphs. (orig.)