Coloring Graph with some constarints

Question

if Graph G be a Cycle with Length=4. how many ways we can color this graph with at most $\lambda$ different color, in such a way that non of two adjacent vertex has a same color?

Answer 1

If the cycle is $abcd$, where $a,b,c,d$ are vertices of the graph, the possible coloring patterns are $xyxy$, $xyxz$, $xyzy$, $xyzw$ where $x,y,z,w$ are different colors. (Of course if you only have $\lambda=2 \text{ or } 3$ colors available, not all these patterns are achievable.)

For the first pattern, choose a color for $x$, choose a color for $y$. This can be done in $\lambda\cdot(\lambda-1)$ ways.

For the second pattern, choose a color for $x$, a color for $y$, a color for $z$. This can be done in $\lambda\cdot(\lambda-1)\cdot(\lambda -2)$ ways. (Note: If $\lambda<3$, this works out to $0$, which makes sense.

The third and fourth patterns are similar.

I think you end up with $\lambda\cdot(\lambda-1)+\lambda\cdot(\lambda-1)\cdot(\lambda -2)+\lambda\cdot(\lambda-1)\cdot(\lambda -2)+\lambda\cdot(\lambda-1)\cdot(\lambda -2)\cdot(\lambda-3)$, which should be equal to your answer.

Answer 2

Suppose the vertices of the cycle are $w$, $x$, $y$, and $z$, in that order. You can choose a color for $w$ in $\lambda$ different ways. After choosing the color for $w$, you can choose a color for $x$ in $\lambda-1$ different ways. Now you have two possible choices for $y$:

1. color it the same as $w$ (in 1 way), or

2. color it a different color than $w$ (in $\lambda-1$ ways).

In case (1), you have $\lambda-1$ choices of color for $z$, and so there are $\lambda \cdot (\lambda-1)\cdot 1 \cdot (\lambda-1)$ ways to color. In case (2), you have $\lambda-2$ choices of color for $z$, and so there are $\lambda \cdot (\lambda-1) \cdot (\lambda -1) \cdot (\lambda-2)$ ways to color. So in total you have:

\begin{array}\\ \lambda(\lambda-1)^2 + \lambda (\lambda-1)(\lambda-2)^2 &= \lambda(\lambda-1)(\lambda-1 + (\lambda-2)^2)) \\ &= \lambda(\lambda-1)(\lambda^2 - 3 \lambda + 3) \\ &= \lambda^4 -4\lambda^3 + 6 \lambda^2 - 3 \lambda \end{array}