Is there a graph coloring algorithm where limits can be placed on number of vertices per color

Question

I understand that graph coloring is a NP-complete problem. I was wondering if adding a restriction on the number of vertices that can have a given color makes the problem simpler? I can't seem to find any algorithm which does this. For example if I have a graph, I'd like to say "what is the smallest coloring of this graph such that each color has at most 3 vertices", or if it simplifies the problem "is there a way to color this graph with 4 colors such that each color has at most 3 vertices"?

Thanks!

Answer 1

This problem is still NP-complete by a simple reduction from the original graph coloring problem: a graph with n nodes is k-colorable if and only if the graph can be colored with k colors and no color is assigned to more than n nodes. In other words, the general version of the problem you're phrasing has graph coloring as a special case, and so it will still be NP-hard.

Hope this helps!

Answer 2

I would say that looking for the chromatic number of a graph given the restriction that a k-coloring exists can be easily added to an exact DSATUR based algorithm [Randall-Brown 72] [San Segundo 11] and prune the search space when one vertex has to be assgined color k. In any case the problem remains in NP.