Grytczuk's conjecture on bounded nonrepetitive chromatic number of planar graphs

About 15 years old · traced to

Let GG be a graph. A vertex coloring is nonrepetitive if no path has a color sequence of the form s1,s2,…,st,s1,s2,…,sts_1,s_2,\dots,s_t,s_1,s_2,\dots,s_t. Let π(G)\pi(G) denote the minimum number of colors in a nonrepetitive vertex coloring of GG. Grytczuk's conjecture. There is an absolute constant KK such that every planar graph GG satisfies

π(G)≤K.\pi(G)\le K.

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

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.