DMTCS Proceedings, 2005 European Conference on Combinatorics, Graph Theory and Applications (EuroComb '05)

Font Size:  Small  Medium  Large

Nonrepetitive colorings of graphs

Noga Alon, Jarosław Grytczuk


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

Valid XHTML 1.0 Transitional