# Number of $r$-colorings of a path graph with a specific color appearing $k$ times: A budgeted graph coloring

How to count proper vertex colorings of a path graph with $$n$$ vertices using at most $$r$$ colors with the condition that a specific color is used exactly $$k$$ times?

When the condition is relaxed, the answer is $$r(r-1)^{n-1}$$.

When the condition is hold, but the coloring can be improper, the answer is $$\binom{n}{k}(r-1)^{n-k}$$. If it is additionally assumed that the specific color is not used for adjacent vertices, while the other colors can (kind of partially proper coloring), the answer is $$\binom{n+1-k}{k}(r-1)^{n-k}$$.

Is there a closed form solution to it? I find it challenging, while only a simple condition is imposed.

It is also related to budgeted graph coloring studied in this paper.

In general, is there any efficient algorithm that enumerates or counts proper $$r$$-colorings of a given simple graph where the number of times that each color appears is exactly given or lies in a given interval? In the above question, the specific color appears exactly $$k$$ times and there are no restrictions on the other colors.

## 1 Answer

The argument that gives $$\binom{n+1-k}{k}(r-1)^{n-k}$$ can be refined to count proper colorings. The idea is that deleting the $$k$$ vertices colored with the special color leaves, in most cases, $$k+1$$ paths with $$n-k$$ vertices total, and there are $$(r-1)^{k+1}(r-2)^{n-2k-1}$$ ways to color these paths.

We cannot simply say $$\binom{n+1-k}{k}(r-1)^{k+1}(r-2)^{n-2k-1}$$, because if the first and/or the last vertex gets the special color, then fewer components are left over. There are $$\binom{n-k-1}{k-2}$$ cases where both the first and last vertex get the special color, $$2\binom{n-k-1}{k-1}$$ cases where only one of them does, and $$\binom{n-k-1}{k}$$ cases where neither of them does. We can combine these into $$\binom{n-k-1}{k-2}(r-1)^{k-1}(r-2)^{n-2k+1} + 2 \binom{n-k-1}{k-1}(r-1)^k (r-2)^{n-2k} + \binom{n-k-1}{k} (r-1)^{k+1}(r-2)^{n-2k-1}$$ total $$r$$-colorings.

• Thank you Misha, but a slight change is required. $r$ and $r-1$ should be replaced by $r-1$ and $r-2$, respectively as the specific color is one of the $r$ colors.
– Amir
Commented Oct 9, 2023 at 15:12
• Hence, the answer is $$\binom{n-k-1}{k-2}(r-1)^{k-1}(r-2)^{n-2k+1} + 2 \binom{n-k-1}{k-1}(r-1)^k (r-2)^{n-2k} + \binom{n-k-1}{k} (r-1)^{k+1}(r-2)^{n-2k-1}$$
– Amir
Commented Oct 9, 2023 at 16:18
• Thank you! I've corrected it. Commented Oct 9, 2023 at 17:36