Non-Repetitive 3-Coloring of Subdivided Graphs

Abstract

We show that every graph can be subdivided in a way that the resulting graph can be colored without repetitions on paths using only 3 colors. This extends the result of Thue asserting the existence of arbitrarily long nonrepetitive strings over a 3-letter alphabet.