  Let $G$ be a graph and $v$ any vertex of $G$. We define the degenerate degree
of $v$, denoted by $\zeta(v)$ as $\zeta(v)={\max}_{H: v\in H}~\delta(H)$, where
the maximum is taken over all subgraphs of $G$ containing the vertex $v$. We
show that the degenerate degree sequence of any graph can be determined by an
efficient algorithm. A $k$-independent set in $G$ is any set $S$ of vertices
such that $\Delta(G[S])\leq k$. The largest cardinality of any $k$-independent
set is denoted by $\alpha_k(G)$. For $k\in \{1, 2, 3\}$, we prove that
$\alpha_{k-1}(G)\geq {\sum}_{v\in G} \min \{1, 1/(\zeta(v)+(1/k))\}$. Using the
concept of cheap vertices we strengthen our bound for the independence number.
The resulting lower bounds improve greatly the famous Caro-Wei bound and also
the best known bounds for $\alpha_1(G)$ and $\alpha_2(G)$ for some families of
graphs. We show that the equality in our bound for independence number happens
for a large class of graphs. Our bounds are achieved by Cheap-Greedy algorithms
for $\alpha_k(G)$ which are designed by the concept of cheap sets. At the end,
a bound for $\alpha_k(G)$ is presented, where $G$ is a forest and $k$ an
arbitrary non-negative integer.

Combinatorics