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.

$\endgroup$
4
  • $\begingroup$ Could you please define what you mean by "distinct walks" in this context? That does that have to do with coloring? $\endgroup$
    – hmakholm left over Monica
    Nov 10, 2011 at 15:24
  • $\begingroup$ 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$. $\endgroup$
    – Steve
    Nov 10, 2011 at 15:47
  • $\begingroup$ 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. $\endgroup$
    – James Waldby - jwpat7
    Nov 15, 2011 at 5:10
  • $\begingroup$ Here, $k$ is the number of vertices, not the number of edges. So, when $k=2$, you have $\{br,bg,gr,gb,rg,rb\}$. $\endgroup$
    – Steve
    Nov 15, 2011 at 21:39

2 Answers 2

Reset to default
2
$\begingroup$

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

$\endgroup$
6
  • $\begingroup$ Suppose 0101...012 colouring. If $n>5$, isn't 201012 also excluded? $\endgroup$
    – Steve
    Nov 11, 2011 at 19:12
  • $\begingroup$ Yes, correction added. $\endgroup$
    – David Bevan
    Nov 12, 2011 at 9:29
  • $\begingroup$ 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? $\endgroup$
    – Steve
    Nov 12, 2011 at 11:13
  • $\begingroup$ Apologies (too quick to generalise). Will correct again. $\endgroup$
    – David Bevan
    Nov 12, 2011 at 17:30
  • $\begingroup$ 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). $\endgroup$
    – David Bevan
    Nov 12, 2011 at 18:03
1
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ 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. $\endgroup$
    – Steve
    Nov 11, 2011 at 13:14
  • $\begingroup$ 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. $\endgroup$
    – David Bevan
    Nov 11, 2011 at 13:18
  • $\begingroup$ 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? $\endgroup$
    – Steve
    Nov 11, 2011 at 13:31
  • $\begingroup$ 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. $\endgroup$
    – David Bevan
    Nov 11, 2011 at 14:56
  • $\begingroup$ 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$? $\endgroup$
    – Steve
    Nov 11, 2011 at 15:05

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .