International Journal of Mathematics and Mathematical Sciences
Volume 2007 (2007), Article ID 74639, 10 pages
doi:10.1155/2007/74639

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.