Vertex coloring of plane graphs with nonrepetitive boundary paths

Abstract

A sequence $s_1,s_2,...,s_k,s_1,s_2,...,s_k$ is a repetition. A sequence $S$ is nonrepetitive, if no subsequence of consecutive terms of $S$ form a repetition. Let $G$ be a vertex colored graph. A path of $G$ is nonrepetitive, if the sequence of colors on its vertices is nonrepetitive. If $G$ is a plane graph, then a facial nonrepetitive vertex coloring of $G$ is a vertex coloring such that any facial path is nonrepetitive. Let ${\pi }_f(G)$ denote the minimum number of colors of a facial nonrepetitive vertex coloring of $G$. Jendro\vl and Harant posed a conjecture that ${\pi }_f(G)$ can be bounded from above by a constant. We prove that ${\pi }_f(G)\le 24$ for any plane graph $G$.

References in corpus (1)

• Vertex coloring of plane graphs with nonrepetitive boundary paths

Cited by in corpus (12)

• Nonrepetitive Colouring via Entropy Compression
• Entropy compression method applied to graph colorings
• Planar graphs have bounded nonrepetitive chromatic number
• On the facial Thue choice index via entropy compression
• Vertex coloring of plane graphs with nonrepetitive boundary paths
• Nonrepetitive Colourings of Planar Graphs with $O(\log n)$ Colours
• On the facial Thue choice number of plane graphs via entropy compression method
• Nonrepetitive colourings of graphs excluding a fixed immersion or topological minor
• The Thue choice number versus the Thue chromatic number of graphs
• Nonrepetitive graph colouring
• Plane Graphs are Facially-non-repetitively $10^{4\cdot 10^7}$-Choosable
• Total Thue colourings of graphs