### Nonrepetitive colorings of graphs

*Noga Alon, Jarosław Grytczuk*

#### Abstract

A vertex coloring of a graph G is k

*-nonrepetitive*if one cannot find a periodic sequence with k blocks on any simple path of G. The minimum number of colors needed for such coloring is denoted by πk(G) . This idea combines graph colorings with Thue sequences introduced at the beginning of 20th century. In particular Thue proved that if G is a simple path of any length greater than 4 then π2(G)=3 and π3(G)=2. We investigate πk(G) for other classes of graphs. Particularly interesting open problem is to decide if there is, possibly huge, k such that πk(G) is bounded for planar graphs.Full Text: GZIP Compressed PostScript PostScript PDF original HTML abstract page