International Journal of Mathematics and Mathematical Sciences
Volume 2007 (2007), Article ID 74639, 10 pages
doi:10.1155/2007/74639
Review Article
Nonrepetitive Colorings of Graphs—A Survey
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.
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.