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 &quot;good&quot; 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$?
A partition of a graph into independent set is the same as graph coloring. Therefore we can reformulate your question as follows:

Can we bound the chromatic number of a graph in terms of its maximum degree?

If every vertex has at most $c$ different neighbors, then the chromatic number is at most $c+1$, and this can be achieved using a greedy approach: scan the vertices in an arbitrary order, and color each vertex in a color different from all its already colored neighbors (this will always succeed since there are $c+1$ possible colors and only $c$ potential already colored neighbors).
There are graphs with maximum degree $c$ which have chromatic number $c+1$, for example the clique $K_{c+1}$ on $c+1$ vertices, so this bound is tight.