Question About Divisors Of Coloring Polygons

Question

I've done a lot of questions about coloring, so I have a question about this.
If an $n-$gon's vertices can be colored with $c$ distinct colors with no adjacent vertices being the same in $a$ ways, then does
(a) $c|a?$
(b) $(c-1)|a?$
(for all $a,c$)
I would say $(a)$ is true since you can shift the colors, but then with that same argument I can say $c!|a$ by using permutations. What is my error of reasoning?
(b) It seems this is always true, although this isn't intuitive. Could someone explain this?

Answer 1

You can't conclude that $c! \mid a$ because not all permutations of the colors will actually change the coloring of the polygon. For example, if I color the vertices alternately red and blue, and you switch the colors green and purple, you haven't changed the coloring.

(In other words, you've divided up the set of colorings that use all $c$ colors at least once into groups of $c!$. The number of colorings that don't use all colors might not be divisible by $c!$, however.)

It is always true that shifting all the colors forward by one will change the coloring, because all colors will change. So your argument that $c \mid a$ is correct.

To argue that $c-1 \mid a$, we can use a slightly different shift. Leave the first color alone, and shift all other colors forward by one (shifting the last color to the second color). This still must always change the coloring, since there is no valid coloring that only uses the first color. So this shift partitions the colorings into cycles of $c-1$.