Question

Let $G$ be an undirected odd cycle. Let $f$ be a proper 3-coloring of $G$. If $w=v_1v_2...v_k$ is a walk on $k$ vertices of $G$, let $f(w)=f(v_1)f(v_2)...f(v_k)$. Let $W_k=\{f(w)|w$ is a walk on $k$ vertices in $G\}$. Let $|W_k|$ be the cardinality of $W_k$.

Is it true that $\lim_{k \to \infty} \frac{\log |W_k|}{k}=\log 2$ regardless of the order of $G$ and the choice of $f$?

Thank you.

Answer 1

Certainly not. Take the coloring that is alternating black and white, except for a single red.