Nonrepetitive Colorings of Graphs—A Survey

A vertex coloring f of a graph G is nonrepetitive if there are nointeger r≥1 and a simple path v1,…,v2r in G such that f(vi)=f(vr+i) for all i=1,…,r. This notion is a graph-theoretic variant of nonrepetitive sequences of Thue. The paper surveysproblems and results on this topic