Facial Rainbow Coloring of Plane Graphs

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

Keywords

• cyclic coloring
• rainbow coloring
• plane graphs
• 05c10
• 05c15