# chromatic polynomial of a path with harmonious coloring application

Harmonious coloring is defined as a (proper) vertex coloring in which every pair of colors appears on at most one pair of adjacent vertices. So given a path that contains $$5$$ vertices, we have assigned chromatic polynomial or ways to color a vertex using the definition of the harmonious coloring. So this is what we have come up to: Is my way of assigning the ways to color the vertex is correct? Do I achieve a correct chromatic polynomial for a path using the definition of harmonious coloring?

Next, we have is a path with 11 vertices, the same application of the harmonious definition. Consider that this is a path where the assigned colors are the vertices.

red -- blue -- green -- black -- white -- red -- black -- blue -- white -- green -- red

what chromatic poly we can achieve in here?

For the 3 first nodes, you are right, three colors must be distinct, be after, it gets more complicated. Let $$a,b,c,d,e$$ be the colors on the nodes of the path (in that order). Let say we fix $$a,b,c$$ to 3 distinct colors. Then, there is two cases for d:
$$d = a$$ then $$e$$ can take any value except $$a,b$$ and $$c$$.
$$d \neq a,b,c$$, then $$e$$ can take any value except $$c$$ and $$d$$.
So we get the polynomial $$k(k-1)(k-2)[1\times(k-3) + (k-3)(k-2)] = k(k-1)^2(k-2)(k-3)$$.
For 11 vertices, this seems to be very tedious to compute, but we can continue like this. For example, for 6 vertices, I get $$k(k-1)(k-2)\left[(k-3)(k-2) + (k-3)\left[(k-3) + (k-4) + (k-4)(k-2)\right]\right] = k(k-1)(k-2)(k-3)(k^2-3k-1)$$
• I wrote a short Mathematica program that confirms your $6$-vertex polynomial, and gets $k(k-1)(k-2)(k-3)(k-4)(k^6-9 k^5-12 k^4+292 k^3-547 k^2-995 k+2172)$ for the $11$-vertex path. Feb 3, 2022 at 20:19