<p><a href="https://arxiv.org/abs/2110.14498" rel="nofollow noreferrer">This WALCOM 2022</a> paper by Bandopadhyay <em>et al</em>. introduces the variant of Coloring (that they refer to as &quot;Budgeted Graph Coloring&quot;) that you are looking for!</p>
<p>Here is a summary of their results:</p>
<ul>
<li>It is NP-Hard even for 3 colors when restricted to bipartite graphs.</li>
<li>It can be solved in polynomial time when restricted to cluster graphs.</li>
<li>It is NP-hard when restricted to split graphs (which subsumes the family of both interval graphs and perfect graphs) and co-cluster graphs.</li>
</ul>
<p>They also provide some FPT results when the problem is parameterized by some common structural parameters such as vertex cover, clique modulator size, (cluster vertex deletion size, number of colors), and (cluster vertex deletion size, number of clusters).</p>

CC BY-SA 4.0
2022-10-09T22:53:53.663Z
Thanks for the reference; this looks like exactly what I was looking for.
user167622
CC BY-SA 4.0
2022-10-10T16:59:47.620Z
we'd like to acknowledge you in our acknowledgements, if you'd like to be acknowledged, please email tcsstudent11235@gmail.com.
user167622
CC BY-SA 4.0
2022-10-09T03:19:26.920Z
2022-10-09T03:19:26.920Z
KPN
<p>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 <span class="math-container">$C = (c_1, \dots, c_k)$</span> where each color <span class="math-container">$c_i$</span> is associated with a bound on the number of times it can be used <span class="math-container">$b_i$</span> (where there can be at most <span class="math-container">$b_i$</span> nodes colored with color <span class="math-container">$c_i$</span>) 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.</p>
<p>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.</p>

CC BY-SA 4.0
2022-10-07T20:12:59.667Z
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.
Dmitry
CC BY-SA 4.0
2022-10-08T15:25:39.890Z
@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.
user167622
<ds.algorithms><graph-colouring>
Graph coloring with limit on number of times a color is used
user167622
# Graph coloring with limit on number of times a color is used

(Asked by: username_0 on 2022-10-07)

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.

**Tags:** ds.algorithms, graph-colouring

> **Comments:**
> **username_1**: 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.  
> **username_0**: @username_1 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.  

---

## 1 answers

### Answer by username_2 on 2022-10-09. Score: 3 | Accepted answer

[This WALCOM 2022](https://arxiv.org/abs/2110.14498) paper by Bandopadhyay *et al*. introduces the variant of Coloring (that they refer to as "Budgeted Graph Coloring") that you are looking for!

Here is a summary of their results:

* It is NP-Hard even for 3 colors when restricted to bipartite graphs.
* It can be solved in polynomial time when restricted to cluster graphs.
* It is NP-hard when restricted to split graphs (which subsumes the family of both interval graphs and perfect graphs) and co-cluster graphs.

They also provide some FPT results when the problem is parameterized by some common structural parameters such as vertex cover, clique modulator size, (cluster vertex deletion size, number of colors), and (cluster vertex deletion size, number of clusters).

> **Comments:**
> **username_0**: Thanks for the reference; this looks like exactly what I was looking for.  
> **username_0**: we'd like to acknowledge you in our acknowledgements, if you'd like to be acknowledged, please email tcsstudent11235@gmail.com.  

---

