Vertex coloring of plane graphs with nonrepetitive boundary paths

Details Vertex coloring of plane graphs with nonrepetitive boundary paths Vertex coloring of plane graphs with nonrepetitive boundary paths

2011-05-05

arxiv.org/abs/1105.1023v1

Mathematics

Combinatorics

Scientific paper

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$.

Affiliated with

Also associated with

No associations

Rating

Vertex coloring of plane graphs with nonrepetitive boundary paths does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Vertex coloring of plane graphs with nonrepetitive boundary paths, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Vertex coloring of plane graphs with nonrepetitive boundary paths will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-690528