Grytczuk's bounded Thue number conjecture for planar graphs

About 14 years old · traced to

For a graph GG, a nonrepetitive coloring is a coloring f:V(G)→Nf:V(G)\to\mathbb N with no repetition in the color sequence of any simple path in GG. The minimum number of colors in such a coloring is the Thue number pi(G)pi(G).

Grytczuk's conjecture. There is a constant cc such that

π(G)⩽c\pi(G)\leqslant c

for all planar graphs GG. 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

Never refreshed

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.