On nonrepetitive colorings of cycles.

We say that a sequence a 1... a 2t of integers is repetitive if a i = a i+t for every i ϵ {1,...,t}. A walk in a graph G is a sequence v 1... v r of vertices of G in which v i v i+1 ϵ E(G) for every i ϵ {1,..., r - 1}. Given a k -coloring c: V(G) → {1,..., k } of V(G) , we say that c is walk-nonrepetitive if for every t ϵ N, for every walk v 1... v 2t in G the sequence c(V 1)... c(v 2t) is not repetitive unless v i = v i+t for every i ϵ {1,..., t }, and the walk-nonrepetitive chromatic number σ (G) of G is the minimum k for which G has a walk-nonrepetitive k-coloring. Let C n denote the cycle with n vertices. In this paper we show that σ(C n) = 4 whenever n ≥ 4 and n ∉ {5,7}, which answers a question posed by Barát and Wood in 2008. [ABSTRACT FROM AUTHOR]