Facial rainbow coloring of plane graphs
Stanislav Jendrol′, Lucia Kekeňáková · Discussiones Mathematicae Graph Theory · 2018
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 ) 3 2 L(T ) for any tree T and rb(G) 5 3 L(G) 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.