# parallel computing – Repeatedly finding and deleting maximal independent sets on a graph: Number of necessary iterations in restricted cases

I am trying to design a parallel scheduling algorithm based on a constraint graph $$G=(V,E)$$ in which each node represents a task and each edge $$e=(v_1, v_2)$$ signifies, that tasks $$v_1$$ and $$v_2$$ can not be executed in parallel. Each task is executed exactly once, so the problem is finding “good” independent sets $$V_i$$, so that

$$bigcup_{i=1}^{k} V_i = V\$$

with all independent sets $$V_i, V_j$$ being pairwise disjoint. Since MaxIS is NP-Hard my approach would be solving MIS repeatedly (finding some maximal independent set, removing those vertices and start again until the Graph is empty). I know that in the worst case of $$G$$ being a clique this approach would yield $$n$$ iterations, however in my instance i would have the guarantee that the number of neighbors of each node would be upper-bound by $$c ll |V|$$.

My question is: Given such a $$c$$ is there any upper bound on the number of necessary steps $$k$$?