The number of 3-coloring methods of a graph

Question

Given a graph with $2n$ nodes named by $u_1,u_2\cdots u_n$ and $v_1,v_2\cdots v_n$.

The graph is given like this: $\forall 1\le i\le n$, there is an edge between $u_i$ and $v_i$, and there is also an edge between $u_i$ and $u_{i+1}$ as well as $v_i$ and $v_{i+1}$($u_{n+1}$ is considered as $u_1$, so as $v_{n+1}$). My question is, how many method are there to color the graph with three colors?

By doing some experiment, denote the number of method by $C(n)$, I know that it follows a recurrence equation(I know it by a experiment result of testing $n=3,4,\cdots 10$, not giving a precise proof) $C(n)=2C(n-1)+5C(n-2)-6C(n-3),C(3)=12,C(4)=114,C(5)=180$. I have tried induction, but without any idea of proving this recurrence equation, any hints or solutions are welcomed. Thanks for attention!

Answer 1

Call the three colors $0$, $1$, $2$. Each rung $(u_i,v_i)$ of your "circular ladder" can then be colored in one of the six ways $01$, $12$, $20$, $10$, $21$, $02$. Assume $(u_0,v_0)$ is colored $01$. Each admissible coloring of the full ladder then corresponds to a closed path $\gamma$ of length $n$ beginning and ending at the node $01$ in the following auxiliary graph:

Count a counterclockwise movement along a leg of one of the triangles as $+1$ and a clockwise movement as $-1$. If $\gamma$ contains $m\leq n$ movements along a triangle leg, counting $x_i\in\{-1,1\}$ $\ (1\leq i\leq m)$, then we must have $$\sum_{i=1}^m x_i=0\quad({\rm mod}\ 3)\ .\qquad(*)$$ Given $m$ it is easy to verify by induction that the number of solutions of $(*)$ is $$b_m={1\over3}\bigl(2^m +2(-1)^m\bigr)\ .$$

The closed path $\gamma$ has to contain an even number of changes from the outer to the inner triangle or vice versa. Given $k$ with $0\leq k\leq\lfloor{n\over2}\rfloor$ the $2k$ jump times can be chosen in ${n\choose 2k}$ ways.

Dropping the assumption that the rung $(u_0,v_0)$ is colored $01$ we therefore get a total of $$C(n)=6 \sum_{k=0}^{\lfloor n/2\rfloor} {n\choose 2k} b_{n-2k}=2 \sum_{k=0}^{\lfloor n/2\rfloor} {n\choose 2k}\bigl(2^{n-2k}+2(-1)^n\bigr)$$ such paths, resp., admissible colorings of our circular ladder.

Using the formula $$2\sum_{k=0}^{\lfloor n/2\rfloor} {n\choose 2k} x^{2k}=(1+x)^n+(1-x)^n$$ this can be simplified to $$C(n)=3^n+2(-1)^n\>2^{n+1} +1\ .$$ The conjectured recurrence for the $C(n)$ can now be verified a posteriori. It would be nice to have a "direct" proof of it.

Answer 2

Let $a_n$, $b_n$, $c_n$ and $d_n$ denote the numbers of paths in Christian's graph that begin at $01$ and end at $20$, $02$, $01$ and $10$, respectively. (By symmetry, $a_n$ and $b_n$ are also the numbers of paths that begin at $01$ and end at $12$ and $21$, respectively.) Extending the paths by one edge yields the following recurrences for $n\ge1$:

$$ a_n=a_{n-1}+b_{n-1}+c_{n-1}\;,\\ b_n=a_{n-1}+b_{n-1}+d_{n-1}\;,\\ c_n=a_{n-1}+a_{n-1}+d_{n-1}\;,\\ d_n=b_{n-1}+b_{n-1}+c_{n-1}\;. $$

The sum of the first two right-hand sides is equal to the sum of the last two right-hand sides, so $a_n+b_n=c_n+d_n=:f_n$ for $n\ge1$; then either sum yields $f_n=3f_{n-1}$ for $n\ge2$.

Subtracting the second equation from the first yields $a_n-b_n=c_{n-1}-d_{n-1}$ for $n\ge1$, and then subtracting the fourth from the third and substituting for $a_{n-1}-b_{n-1}$ yields $g_n=-g_{n-1}+2g_{n-2}$ for $n\ge2$, with $g_n:=c_n-d_n$.

With $a_0=0$, $b_0=0$, $c_0=1$, $d_0=0$ and $a_1=1$, $b_1=0$, $c_1=0$, $d_1=1$ the initial values are $f_1=1$, $g_0=1$, $g_1=-1$, and the recurrences can be solved by the method applied in my other answer. The result is $3f_n=3^n$ and $3g_n=1-(-2)^{n+1}$, and so

$$C(n)=6c_n=3(f_n+g_n)=3^n-(-2)^{n+1}+1\;.$$

Answer 3

The standard method for solving such a recurrence is to make the ansatz $C(n)=\lambda^n$ and solve the resulting characteristic equation, $\lambda^3-2\lambda^2-5\lambda+6=0$. The solution $\lambda=1$ can be guessed and factored out, leaving $\lambda^2-\lambda-6=0$ with solutions $\lambda=-2$ and $\lambda=3$. The general solution is then obtained as a linear superposition of these solutions, $C(n)=c_1+c_2(-2)^n+c_33^n$. Your initial values yield a system of linear equations,

$$ \begin{align} c_1-8c_2+27c_3=12\;,\\ c_1+16c_2+81c_3=114\;,\\ c_1-32c_2+243c_3=180\;, \end{align} $$

with solution $c_1=1$, $c_2=2$, $c_3=1$. Thus the number of colourings is

$$C(n)=1-(-2)^{n+1}+3^n\;.$$

This result is also correct for $n=1$ and $n=2$ (if we interpret the edges from $u_1$ to $u_1$ and $v_1$ to $v_1$ in the case $n=1$ as self-loops preventing the vertices from having any colour at all), so with hindsight the solution of the recurrence could have been simplified by using $C(1)$, $C(2)$ and $C(3)$ as initial values instead.