A sequence of the form s1 s2 ... sM s1 s2 ... sM is called a repetition. A vertex-coloring of a graph is called nonrepetitive if none of its paths is repetitively colored. We have shown that outerplanar graphs have nonrepetitive 12-colorings (answering a question of Grytczuk) and graphs of treewidth t have nonrepetitive 4^t-colorings. I'll also discuss some related topics and give some open questions in this area.
(Joint work with Andre Kundgen)