Nonrepetitive Colorings of Graphs—A Survey

Abstract

A vertex coloring f of a graph G is nonrepetitive if there are no integer 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 surveys problems and results on this topic.