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
Status
- Solved: Vida Dujmović, Louis Esperet, Gwenaël Joret, Bartosz Walczak, and David R. Wood. Planar graphs have bounded nonrepetitive chromatic number (Advances in Combinatorics, 2020) https://www.advancesincombinatorics.com/article/12100-planar-graphs-have-bounded-nonrepetitive-chromatic-number
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.