Jaroslaw Grytczuk: Nonrepetitive colorings of graphs

A colored path P is repetitive if the sequence of colors on the first half of P is the same as the sequence of colors on the second half of P. A coloring of a graph G is nonrepetitive if there is no repetitive path in G.

This notion was introduced in 2002 as a graph theoretic variation on the theorem of Thue on words without repetitions. A major open problem in this area is whether planar graphs are nonrepetitively colorable with a bounded number of colors. I will present some recent results towards resolution of this question. Particularly promising seems to be a newly developed approach, called entropy compression, that appears to be useful also for other types of graph colorings.