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.