# Graph coloring with limit on number of times a color is used

Are there any results on coloring a graph using a limited number of each color. In other words, the decision problem would be: given a list of colors $$C = (c_1, \dots, c_k)$$ where each color $$c_i$$ is associated with a bound on the number of times it can be used $$b_i$$ (where there can be at most $$b_i$$ nodes colored with color $$c_i$$) can you color the vertices of a graph where no two adjacent vertices are colored the same color. This decision problem is NP-hard when there are no constraints on the number of times a color is used so it is also hard in this setting.

But has this problem been studied in graphs where chromatic number is easy such as interval graphs or perfect graphs? It is not clear to me that this problem is easy on graph classes where finding the chromatic number is polynomial time.

• 1) Are you interested in the case when $k$ is fixed? 2) If there exists a class of graphs for which it's trivial to check that it's $k$-corolable, but it's NP-hard to solve your problem, does it answer your question? What I have in mind is a graph where each connected component can be split into $k$ parts $A_1, \ldots, A_k$ such that each $A_i$ is an anti-clique, and there are all possible edges between $A_i$ and $A_j$ for all $i,j$. Then, depending on the first question, we might show NP-hardness via reduction from some subset-sum-like problem. Oct 7, 2022 at 20:12
• @Dmitry 1) Yes, I am interested in the case when $k$ is fixed. 2) Yes, this does sound interesting. However, I am more interested in the interval graph case, for which there is a known simple greedy solution but that particular greedy solution doesn't work for this problem. Oct 8, 2022 at 15:25