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?


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$.

  • $\begingroup$ 1st paragraph: I believe you mean that there are multiple permutations that make red and blue alternating into green and purple alternating that are all considered the same. $\endgroup$
    – Jason Kim
    Aug 22 '18 at 2:25
  • $\begingroup$ Both of those are true, and in fact the two claims are equivalent. (In technical language, the permutation group does not act faithfully on the set of colorings.) $\endgroup$ Aug 22 '18 at 4:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.