The page-number-2 conjecture for nonrepetitive graph coloring

At least 13 years old · documented by

A graph has page number kk if its vertices can be arranged on a spine and its edges partitioned into kk pages, with no two edges on the same page crossing in the spine order. A vertex coloring is nonrepetitive if no path has a color sequence of the form XXXX for a nonempty word XX. Page-number-2 conjecture. There is a finite constant NN such that every graph of page number 22 has a nonrepetitive coloring using NN colors.

This question was propounded by Idziak and is presented as a major open problem in nonrepetitive graph coloring. The paper notes that it would imply the existence of a bounded nonrepetitive coloring for planar graphs.

References

Primary source

Jarosław Grytczuk, Piotr Szafruga and Michał Zmarz, “Online version of the theorem of Thue”, arXiv:1204.6687 (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.