×

Non-repetitive 3-coloring of subdivided graphs. (English) Zbl 1165.05325

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.

MSC:

05C15 Coloring of graphs and hypergraphs
PDF BibTeX XML Cite
Full Text: EuDML EMIS