Let $G = (V,E)$ be a graph and $k \ge 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) \ge \frac{k+1}{\lceil d \rceil + k + 1} n$, improving the hitherto best general lower bound due to Caro and Tuza [Improved lower bounds on $k$-independence, J. Graph Theory 15 (1991), 99-107].
@article{10_37236_2646,
author = {Yair Caro and Adriana Hansberg},
title = {New approach to the \(k\)-independence number of a graph},
journal = {The electronic journal of combinatorics},
year = {2013},
volume = {20},
number = {1},
doi = {10.37236/2646},
zbl = {1266.05110},
url = {http://geodesic.mathdoc.fr/articles/10.37236/2646/}
}
TY - JOUR
AU - Yair Caro
AU - Adriana Hansberg
TI - New approach to the \(k\)-independence number of a graph
JO - The electronic journal of combinatorics
PY - 2013
VL - 20
IS - 1
UR - http://geodesic.mathdoc.fr/articles/10.37236/2646/
DO - 10.37236/2646
ID - 10_37236_2646
ER -
%0 Journal Article
%A Yair Caro
%A Adriana Hansberg
%T New approach to the \(k\)-independence number of a graph
%J The electronic journal of combinatorics
%D 2013
%V 20
%N 1
%U http://geodesic.mathdoc.fr/articles/10.37236/2646/
%R 10.37236/2646
%F 10_37236_2646
Yair Caro; Adriana Hansberg. New approach to the \(k\)-independence number of a graph. The electronic journal of combinatorics, Tome 20 (2013) no. 1. doi: 10.37236/2646
