Coloring problem with limited number of each colors.

Question

I’m investigating graph coloring problem.
But I cannot find any solution about the problem with limited number of each colors. I mean, Suppose three colors(green, red, blue) and a graph, we start to color each vertex, but (If green color’s limit is 3) we cannot color as green after we already used green 3 times.
Any comments about this problem will be appreciated. Any papers, articles, or maybe the solution itself.

Thank you for advance.

---

To simplify and clarify the question, I desinged a coarse example.
(vertex coloring. NOT edge coloring)

1) We have 3 colors, let’s say green, blue, red. And the graph is just a line. Every vertex has two edges except only two(=start one, and end one). I mean this : ○-○-○-○-○-○-○. $V$ is the vertex number. In this case $V=7$. We start to coloring each vertex, but the limit is 3, 2, 2.(For simplicity, sum of limits are same with the number of vertexes.) So we can use only 3 greens, 2 blues, 2 reds.(Surely all colors must not be adjacent).
The answer should be 38.(found by checking all combinations)

2) How about a ring graph( so all vertexes have two edges.) in above case?

3) How about a perterson graph with limits 4, 3, 3?

---

I don’t expect the elegant($\approx$short) solution. I’m just curious about the way how to solve this correctly, and wish to break this problem without finding ALL possible cases and check them one by one. Maybe some (tedious) $nCr$s would be nice. If the vertex number and number of colors are limited(eg. $<1000$), time complexity might not be a big problem. (We cannot check every cases even in this small size. Combination’s complexity is in factorial order.$\approx 1000!$) I believe this can be possible using progression, induction or something like that.

Answer 1

Since equitable coloring (thanks to @SteveKass for the pointer) is NP-complete and is polynomially reducible to the OP's problem, the latter is also NP-complete. (Membership in NP is clear.)

It may not be the fastest approach in practice, but encoding the problem so that it may be passed to a propositional SAT solver or an SMT solver may work reasonably well and does not require much coding. I tried Z3 on the Petersen graph just for fun and I got the following solution:

$$ \begin{align} V &= \{0,\ldots,9\} \\ E &= \{(0,5), (1,6), (2,7), (3,8), (4,9), (5,6), (6,7), (7,8), (8,9), (9,5),\\ &\quad\quad (0,2), (2,4), (4,1), (1,3), (3,0)\} \\ C &= \{(0,R), (1,R), (2,B), (3,B), (4,G), (5,B), (6,G), (7,R), (8,G), (9,R)\} \enspace, \end{align} $$ where $C \subseteq V \times \{R,G,B\}$ is the color relation. The problem is tiny; hence the solution time is negligible. I also verified that there is no solution with bounds $(4,4,2)$.

---

If we want to count the solutions, we can add a clause to the SAT query that rules out the solution just found and repeat the satisfiability check until the formula becomes unsatisfiable.

For the Petersen graph this process produces 40 solutions. However, the graph has rotational and mirror symmetries, while the two "3-colors" (those we can use only three times) are interchangeable. From each valid coloring we can therefore obtain $5 \times 2 \times 2 = 20$ colorings.

To get the SAT query to return only solutions that cannot be obtained from other solutions by rotation, symmetry, or color swap, we can add constraints that effectively fix the coloring of the "inner star" of the graph.

A moment's thought shows that there is only one way to color the inner star "modulo graph and color symmetries." Two adjacent points of the star must carry the 4-color, two more adjacent points must carry one of the 3-colors, and the fifth point must carry the other 3-color. There are 20 ways to do that, but they are all related by symmetries.

Given the coloring of the inner star, there are two ways to color the outer pentagon. Besides the one shown above, the SAT solver returns

$$ C = \{(0,R), (1,R), (2,B), (3,B), (4,G), (5,G), (6,B), (7,R), (8,G), (9,R)\} \enspace. $$