Lower bounds for the independence and kk-independence number of graphs using the concept of degenerate degrees

Let GG be a graph and vv be any vertex of GG. We define the degenerate degree of vv, denoted by ζ(v)ζ(v) as ζ(v)=maxH:v∈Hδ(H), where the maximum is taken over all subgraphs of GG containing the vertex vv. We show that the degenerate degree sequence of any graph can be determined by an efficient algorithm. A kk-independent set in GG is any set SS of vertices such that Δ(G[S])≤kΔ(G[S])≤k. The largest cardinality of any kk-independent set is denoted by αk(G)αk(G). For k∈{1,2,3}k∈{1,2,3}, we prove that αk−1(G)≥∑v∈Gmin{1,1/(ζ(v)+(1/k))}αk−1(G)≥∑v∈Gmin{1,1/(ζ(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 α1(G)α1(G) and α2(G)α2(G) for some families of graphs. We show that the equality in our bound for the independence number happens for a large class of graphs. Our bounds are achieved by Cheap-Greedy algorithms for αk(G)αk(G) which are designed by the concept of cheap sets. At the end, a bound for αk(G)αk(G) is presented, where GG is a forest and kk an arbitrary non-negative integer.