4
$\begingroup$

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.

  • 0
    Here, $k$ is the number of vertices, not the number of edges. So, when $k=2$, you have $\{br,bg,gr,gb,rg,rb\}$.2011-11-15

2 Answers 2

2

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

  • 0
    Thank you again David. I have another follow up question, but I will post it as a new question.2011-11-13
1

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.

  • 0
    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$?2011-11-11