Thue type problems for graphs, points, and numbers

A sequence S = S-1 S-2... S-n is said to be nonrepetitive if no two adjacent blocks of S are the same. A celebrated 1906 theorem of Thue asserts that there are arbitrarily long nonrepetitive sequences over the set {0, 1, 2}. This result is the starting point of Combinatorics on Words-a wide area with many deep results, sophisticated methods, important applications and intriguing open problems. The main purpose of this survey is to present a range of new directions relating Thue sequences more closely to Graph Theory, Combinatorial Geometry, and Number Theory. For instance, one may consider graph colorings avoiding repetitions on paths, or colorings of points in the plane avoiding repetitions on straight lines. Besides presenting a variety of new challenges we also recall some older problems of this area. (C) 2007 Elsevier B.V. All rights reserved.