Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question
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$).

share|cite|improve this answer
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.

share|cite|improve this answer
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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.