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

• It seems as though you are looking for this answer: cs.stackexchange.com/questions/115040/… Apr 1, 2021 at 23:30
• Thank you so much. This is exactly what I was looking for. Apr 1, 2021 at 23:44

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.