K-independence and the K-residue of a graph

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.)Available from TIB Hannover: RN 4052(97861) / FIZ - Fachinformationszzentrum Karlsruhe / TIB - Technische InformationsbibliothekSIGLEDEGerman