The page-number-2 conjecture for nonrepetitive graph coloring
A graph has page number if its vertices can be arranged on a spine and its edges partitioned into 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 for a nonempty word . Page-number-2 conjecture. There is a finite constant such that every graph of page number has a nonrepetitive coloring using 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
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.