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

-
Could you please define what you mean by "distinct walks" in this context? That does that have to do with coloring? –  Henning Makholm Nov 10 '11 at 15:24
I am interested in the walks on the colors. So if $f$ is a coloring of $V(G)$, I am interested in counting distinct $f(v_1)f(v_2)..f(v_k)$ where $v_1v_2...v_k$ is a walk on $G$. –  Steve Nov 10 '11 at 15:47
Can you explain your $3*2^{k−1}$ walks on k 3-colored vertices formula? At least at k=1 and k=2 the numbers appear to be twice as large; e.g {br, bg, gr, gb, rg, rb} at k=1, and {gbg, grg, gbr, grb, etc} at k=2. –  jwpat7 Nov 15 '11 at 5:10
Here, $k$ is the number of vertices, not the number of edges. So, when $k=2$, you have $\{br,bg,gr,gb,rg,rb\}$. –  Steve Nov 15 '11 at 21:39

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

-
Suppose 0101...012 colouring. If $n>5$, isn't 201012 also excluded? –  Steve Nov 11 '11 at 19:12
Yes, correction added. –  David Bevan Nov 12 '11 at 9:29
Again suppose odd $n$ and 0101...012 colouring. If $n=7$, 20101012 is not excluded, but for $n>7$ it is. For $n>9$, 2010101012 is excluded, etc. I guess I am not convinced the number is independent of $n$. How did you calculate 1.82462? –  Steve Nov 12 '11 at 11:13
Apologies (too quick to generalise). Will correct again. –  David Bevan Nov 12 '11 at 17:30
I calculated the numeric growth factors by using Mathematica to (a) generate the $W_k$, (b) find the linear difference equation, and (c) numerically find the roots of the resultant "characteristic polynomial". For the $C_5$ example, the polynomial is $x^4 - x^3 - 2 x^2 + 2 x - 2 = 0$; for the $C_7$ example, it is $x^6 - x^5 - 2 x^4 + 2 x^3 - 2 x^2 + 2 x - 2 = 0$ (it looks like there's a pattern there). –  David Bevan Nov 12 '11 at 18:03

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.

-
What if we restrict to 3-colorings of odd cycles? Perhaps we can find an asymptotic formula. Say, that for large $k$, there are approximately $m2^{ck/d}$ walks where $m$, $c$ and $d$ are constants, and I suspect $c/d$ is a function of the number of vertices that are adjacent to 2 distinct colours. –  Steve Nov 11 '11 at 13:14
I would have thought that an asymptotic formulae would be easy to determine, but restricting the problem to 3-colourings of odd cycles doesn't enable the original question to be solved. The following 2 colourings of a 9-cycle - $0 1 0 1 0 2 0 1 2$ and $0 1 0 1 2 0 1 0 2$ - have different numbers of 4-walks. –  David Bevan Nov 11 '11 at 13:18
Thank you David. If we consider a proper 3-coloring of an odd cycle $C_n$. Is the asymptotic formula simply $\approx m2^{\frac{dk}{n}}$ where $m$ is some constant and $d$ is the number of vertices adjacent to 2 distinct colors? –  Steve Nov 11 '11 at 13:31
I think it may be rather more complex than that, and will depend on the relationship between $d$, $k$ and $n$. In fact, I'm thinking that we may see phase change behaviour. For example, if $d/n$ is large enough for there to be a run of $2k+1$ adjacent vertices that are all adjacent to 2 distinct colours (e.g. rgbrgb...), then all $3\times 2^{k-1}$ coloured walks are possible. –  David Bevan Nov 11 '11 at 14:56
Let's consider a precise limit as $k \to \infty$. Suppose we fix an odd $n$, fix a proper 3-coloring of $C_n$. Let $d$ be the number of vertices adjacent to 2 colors. Let $W_k$ be the number of walks on $k$ coloured vertices. Is then, $\lim_{k \to \infty} \frac{\log(W_k)}{k}=\frac{d}{n} \log 2$? –  Steve Nov 11 '11 at 15:05