Facial Rainbow Coloring of Plane Graphs

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

Full description

Bibliographic Details
Main Authors: Jendroľ Stanislav, Kekeňáková Lucia
Format: Article
Language:English
Published: University of Zielona Góra 2019-11-01
Series:Discussiones Mathematicae Graph Theory
Subjects:
Online Access:https://doi.org/10.7151/dmgt.2047
Description
Summary: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)≤⌊32L(T)⌋$rb(T) \le \left\lfloor {{3 \over 2}L(T)} \right\rfloor$ for any tree T and rb(G)≤⌈53L(G)⌉$rb(G) \le \left\lceil {{5 \over 3}L(G)} \right\rceil$ 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.
ISSN:2083-5892