Nonrepetitive colorings of graphs -- a survey (Q925326)

Summary: A vertex coloring \(f\) of a graph \(G\) is nonrepetitive if there are no integer \(r\geq 1\) and a simple path \(\nu_1,\dots,\nu_{2r}\) in \(G\) such that \(f(\nu_i)= f(\nu_{r+i})\) for all \(i=1,\dots,r\). This notion is a graph-theoretic variant of nonrepetitive sequences of Thue. The paper surveys problems and results on this topic.