4
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Dmitry
    Oct 7, 2022 at 20:12
  • $\begingroup$ @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. $\endgroup$
    – user167622
    Oct 8, 2022 at 15:25

1 Answer 1

Reset to default
3
$\begingroup$

This WALCOM 2022 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).

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks for the reference; this looks like exactly what I was looking for. $\endgroup$
    – user167622
    Oct 9, 2022 at 22:53
  • 1
    $\begingroup$ we'd like to acknowledge you in our acknowledgements, if you'd like to be acknowledged, please email [email protected]. $\endgroup$
    – user167622
    Oct 10, 2022 at 16:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.