Facial Nonrepetitive Vertex Coloring of Plane Graphs |
| |
Authors: | János Barát Július Czap |
| |
Institution: | 1. DEPARTMENT OF COMPUTER SCIENCE AND SYSTEMS TECHNOLOGY UNIVERSITY OF PANNONIA, EGYETEM u. 10, , 8200 VESZPRéM, HUNGARY;2. SCHOOL OF MATHEMATICAL SCIENCES, MONASH UNIVERSITY, , VICTORIA 3800, AUSTRALIA;3. DEPARTMENT OF APPLIED MATHEMATICS AND BUSINESS INFORMATICS FACULTY OF ECONOMICS, TECHNICAL UNIVERSITY OF KO?ICE NěMCOVEJ 32, , SK‐040 01 KO?ICE, SLOVAKIA |
| |
Abstract: | A sequence 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 denote the minimum number of colors of a facial nonrepetitive vertex coloring of G. Harant and Jendrol’ conjectured that can be bounded from above by a constant. We prove that for any plane graph G. |
| |
Keywords: | nonrepetitive colouring plane graph Thue sequences |
|
|