Grytczuk's bounded Thue number conjecture for planar graphs
For a graph , a nonrepetitive coloring is a coloring with no repetition in the color sequence of any simple path in . The minimum number of colors in such a coloring is the Thue number .
Grytczuk's conjecture. There is a constant such that
for all planar graphs . This conjecture asks whether planar graphs have uniformly bounded Thue number, extending the known boundedness results for trees, outerplanar graphs, and graphs of bounded tree-width. Its resolution is not indicated in the source.
References
Primary source
Jakub Kozik and Piotr Micek, “Nonrepetitive choice number of trees”, arXiv:1207.5155 (2012).
Progress summary
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
No solutions have been posted yet.