Grytczuk's conjecture on bounded nonrepetitive chromatic number of planar graphs
Let be a graph. A vertex coloring is nonrepetitive if no path has a color sequence of the form . Let denote the minimum number of colors in a nonrepetitive vertex coloring of . Grytczuk's conjecture. There is an absolute constant such that every planar graph satisfies
This is identified in the source as a major open problem; the paper resolves the analogous facial-coloring conjecture but does not state a resolution of Grytczuk's planar-graph conjecture.
References
Primary source
János Barát and Július Czap, “Vertex coloring of plane graphs with nonrepetitive boundary paths”, arXiv:1105.1023 (2011).
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.