pith. sign in

arxiv: 1105.1023 · v1 · pith:KNR5MZGFnew · submitted 2011-05-05 · 🧮 math.CO

Vertex coloring of plane graphs with nonrepetitive boundary paths

classification 🧮 math.CO
keywords nonrepetitivevertexcoloringfacialgraphplanesequencecolors
0
0 comments X
read the original 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$.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.