New approach to the \(k\)-independence number of a graph (Q1953418): Difference between revisions

Summary: Let \(G\) = (\(V,E\)) be a graph and \(k \geq 0\) an integer. A \(k\)-independent set \(S \subseteq V\) is a set of vertices such that the maximum degree in the graph induced by \(S\) is at most \(k\). With \(\alpha_k(G)\) we denote the maximum cardinality of a \(k\)-independent set of \(G\). We prove that, for a graph \(G\) on \(n\) vertices and average degree \(d, \alpha_k(G) \geq \frac{k+1}{\lceil d \rceil + k + 1} n\), improving the hitherto best general lower bound due to \textit{Y. Caro} and \textit{Z. Tuza} [J. Graph Theory 15, No. 1, 99--107 (1991; Zbl 0753.68079)].