Improved lower bounds on k‐independence
Yair Caro, Źsolt Tuza · Journal of Graph Theory · 1991
Abstract A vertex set Y in a (hyper)graph is called k‐independent if in the sub(hyper)‐graph induced by Y every vertex is incident to less than k edges. We prove a lower bound for the maximum cardinality of a k‐independent set—in terms of degree sequences—which strengthens and generalizes several previously known results, including Turán's theorem.