Facial nonrepetitive vertex coloring of plane graphs

摘要

A sequence s_1,s_2,?,s_k,s _1,s_2,?,sk is a repetition. A sequence S is nonrepetitive, if no subsequence of consecutive terms of S is a repetition. Let G be a plane graph. That is, a planar graph with a fixed embedding in the plane. A facial path consists of consecutive vertices on the boundary of a face. A facial nonrepetitive vertex coloring of a plane graph G is a vertex coloring such that the colors assigned to the vertices of any facial path form a nonrepetitive sequence. Let π_f(G) denote the minimum number of colors of a facial nonrepetitive vertex coloring of G. Harant and Jendrol' conjectured that π_f (G) can be bounded from above by a constant. We prove that πf (G)≤24 for any plane graph G.