Authors:
S. Jendrol', L. Kekeòáková
Title:
Facial rainbow coloring of plane graphs
Source:
Discussiones Mathematicae Graph Theory
Received 28.03.2017, Revised 19.12.2017, Accepted 19.12.2017, doi: 10.7151/dmgt.2047

Abstract:
A vertex coloring of a plane graph G is a facial rainbow coloring if any two vertices of G connected by a facial path have distinct colors. The facial rainbow number of a plane graph G, denoted by rb(G), is the minimum number of colors that are necessary in any facial rainbow coloring of G. Let L(G) denote the order of a longest facial path in G. In the present note we prove that rb(T) ≤ \left⌊ \frac{3}{2}L(T) \right⌋ for any tree T and rb(G) ≤ \left⌈ \frac{5}{3}L(G) \right⌉ for arbitrary simple graph G. The upper bound for trees is tight. For any simple 3-connected plane graph G we have rb(G) ≤ L(G)+5.
Keywords:
cyclic coloring, rainbow coloring, plane graphs

Links:
PDF