International Journal of Mathematics and Mathematical Sciences
Volume 2007 (2007), Article ID 74639, 10 pages
Review Article

Nonrepetitive Colorings of Graphs—A Survey

Jarosław Grytczuk1,2

1Algorithmics Research Group, Faculty of Mathematics and Computer Science, Jagiellonian University, Kraków 30-387, Poland
2Department of Didactics of Mathematics and Number Theory, Faculty of Mathematics, Computer Science, and Econometrics, University of Zielona Góra, Zielona Góra 65-516, Poland

Received 8 August 2006; Revised 4 November 2006; Accepted 29 November 2006

Academic Editor: George E. Andrews

Copyright © 2007 Jarosław Grytczuk. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.


A vertex coloring f of a graph G is nonrepetitive if there are no integer r1 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.