Pezarski, Andrzej; Zmarz, Michał Non-repetitive 3-coloring of subdivided graphs. (English) Zbl 1165.05325 Electron. J. Comb. 16, No. 1, Research Paper N15, 7 p. (2009). Summary: 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. Cited in 1 ReviewCited in 8 Documents MSC: 05C15 Coloring of graphs and hypergraphs PDFBibTeX XMLCite \textit{A. Pezarski} and \textit{M. Zmarz}, Electron. J. Comb. 16, No. 1, Research Paper N15, 7 p. (2009; Zbl 1165.05325) Full Text: EuDML EMIS