A proper coloring of a graph is defined as an assignment of colors to the vertices of the graph such that for any edge $(v,w)$, $v$ and $w$ have different colors.
Let the number of colors be $4$. Consider a square graph. I am trying to count the number of proper colorings of this graph. Let the colors be $\{0,1,2,3\}$ and the vertices be also $\{0,1,2,3\}$ in the clockwise order with the upper-left vertex being $0$.
My attempt: If we choose $2$ colors to create a proper coloring, then $2$ colors can be chosen from $4$ in $\binom{4}{2}$ ways. For example, consider the following proper coloring $\{0:0,1:1,2:0,3:1\}$. Now a $90^{\circ}$ rotation of this coloring is also a proper coloring which is $\{0:1,1:0,2:1,3:0\}$. Thus there are $\binom{4}{2}\times 2$ proper colorings with two colors.
If we choose $3$ colors, then consider the proper coloring: $\{0:0,1:1,2:2,3:1\}$. Now $3$ rotations of $90^{\circ}$ each give rise to a proper coloring and hence there are $\binom{4}{3}\times 4$ proper colorings with $3$ colors.
If we choose $4$ colors, then there are $4$ proper colorings.
Thus there are $\binom{4}{2}\times 2+\binom{4}{3}\times 4+4$ proper colorings in total. Does that look right? Thanks.
Best Answer
This isn't right: there are $4!$ proper colorings that use all four colors, because the vertex labelled $0$ can be given any of the four possible colors, then the vertex labelled $1$ can be given any of the remaining three colors, and so on.
This is also not entirely correct: notice that for your choice of the three colors as $\{ 0,1,2 \}$, all four colorings that you have found by rotating the specific coloring $\{ 0:0, 1:1, 2:2. 3:1 \}$ have the property that the repeated color is $1$. Rotations will not change the color that is repeated, so you will never get the coloring $\{ 0:1, 1:2, 2:0, 3:2 \}$ via this method. So, for this case, not only do you have to choose a set of three colors, you also need to fix which of the three colors is repeated in a proper coloring, in order to get the correct count.
Your count for the number of proper colorings when only two colors are used is correct. However, for the sake of completeness, you should also show that any proper coloring that uses precisely two colors must arise from one of the configurations that you have described (and similarly when one uses precisely three and four colors). Otherwise, all you have shown is that there are at least as many proper colorings as what you have counted.