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
    Could you please define what you mean by "distinct walks" in this context? That does that have to do with coloring?2011-11-10
  • 0
    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$.2011-11-10
  • 0
    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.2011-11-15
  • 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