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: A line with 5 points, labeled k, (k-1), (k-2), (k-2), and (k-2) (respectively).  Below, the polynomial k(k-1)(k-2)^3.

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?


1 Answer 1


Your polynomial is wrong, for 3 colors, it gives 6, but it is easy to see that it admits no harmonious 3-coloring.
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)$
(If I made no mistakes)

  • 1
    $\begingroup$ 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. $\endgroup$ Feb 3, 2022 at 20:19

You must log in to answer this question.

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