[hal-01184372] Nonrepetitive colorings of graphs

A vertex coloring of a graph G is k\emph-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.

from HAL : Dernières publications http://ift.tt/1UISdlr