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$?