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 1


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.

  • $\begingroup$ 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. $\endgroup$
    – Amir
    Oct 9, 2023 at 15:12
  • $\begingroup$ 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}$$ $\endgroup$
    – Amir
    Oct 9, 2023 at 16:18
  • $\begingroup$ Thank you! I've corrected it. $\endgroup$ Oct 9, 2023 at 17:36

This site is temporarily in read-only mode and not accepting new answers.

Not the answer you're looking for? Browse other questions tagged .