Non-Repetitive 3-Coloring of Subdivided Graphs

  • Andrzej Pezarski
  • Michał Zmarz
DOI: https://doi.org/10.37236/253

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.

Published
2009-05-20
Issue
Volume 16, Issue 1 (2009)
Article Number
N15