Counting walks on colored graphs I am looking for help counting distinct walks on a proper vertex coloring of a graph.  To be more specific, let's consider an odd cycle of order greater than 3 that has been properly 3-colored.  
So, for example, we could color $C_9$ by alternating $r,g,b$ as we moved clockwise around the vertices. Every vertex in $C_9$ is adjacent to two vertices.  With this coloring, every vertex is adjacent to two distinct colors.  The result would be that for any positive integer $k$ there are $(3)(2^{k-1})$ walks on $k$ colored vertices.  Alternatively, we could color one vertex $r$ and then alternate $g,b$ on the others. Now, not every vertex is adjacent to two distinct colors.  For a given $k$, it seems like there should be a formula for the number of walks (on $k$ colored vertices) as a function of the number of vertices that are adjacent to two distinct colors.  However, I am having trouble constructing and proving such a formula.  Any help would be greatly appreciated. Thank you.
 A: The asymptotic growth constant will be dependent on the specific colouring. 
For example, suppose $n=5$ and the colouring is $01012$ (with $d=3$), then $W_k$ counts the walks that exclude the sequences $2012$ and $2102$.
In this case, asymptotically, $W_k$ grows by a factor of about $1.82462$ (in comparison, $2^{3/5}\approx 1.51572$).
Similarly, if $n=7$ and the colouring is $0101012$ (again $d=3$), then $W_k$ counts the walks that exclude the sequences $2012$, $2102$, $201012$ and $210102$.
In this case, asymptotically, $W_k$ grows by a factor of about $1.76540$ (whereas $2^{3/7}\approx 1.34590$).
In fact, the growth factor is nearly always greater than $2^{d/n}$ because even a colouring with minimal $d$ does not exclude many of the possible coloured walks.
As another example, if the colouring is $0101\dots 0121$ (with $d=2$ and even $n$), then $02$ and $20$ are excluded (each walk alternating between $1$ and either $0$ or $2$) giving
$$
W_k\;=\;2^{\lfloor\frac{n}{2}\rfloor}+2^{\lceil\frac{n}{2}\rceil}
$$
with a growth factor of $\sqrt{2}$. In this case the result is independent of $n$ (and hence independent of $d/n$).
A: It isn’t possible to enumerate these walks using only the number of vertices which are adjacent to $2$ distinct colours.
Consider two $4$-coloured copies of $C_6$, one coloured red, yellow, red, yellow, green, blue (or $010123$) and the other coloured red, yellow, green, yellow, red, blue (or $012103$).
Both cycles have the same number of vertices of each colour and the same number ($4$) of vertices that are adjacent to $2$ distinct colours, but the first has $8$ distinct $2$-walks while the second has only $6$ distinct $2$-walks.
Even the ‘adjacency lists’ are not sufficient:
Consider two $5$-coloured copies of $C_7$, one coloured $0 1 0 2 1 3 4$ and the other coloured $0 2 0 1 3 4 1$. They both have the same number of vertices of each colour and the same adjacency list: $(2, 1, 2, 2, 2, 2, 2)$, but the former has  $12$ distinct $2$-walks while the latter has only $10$ distinct $2$-walks.
