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.