Facial Rainbow Edge-Coloring of Plane Graphs

Abstract

An edge-coloring of a loopless plane graph G is a facial rainbow edge-coloring if any two edges of G contained in the same facial path have distinct colors. The facial rainbow edge-number of a graph G, denoted $\mathrm {erb}(G)$, is the minimum number of colors that are necessary in any facial rainbow edge-coloring. In the present note we prove that $\mathrm {erb}(G) \le \lfloor \frac{3}{2} (L(G) + 1) \rfloor$ for all connected loopless plane graphs, where L(G) is the length of the longest facial path of G. This bound is tight. For the family of all 3-connected plane graphs this bound is improved to $L(G) + 2$. For trees there is $\mathrm {erb}(G) \le \lfloor \frac{3}{2} L(G) \rfloor$ which is also tight. Moreover, if G is a tree with $L(G) \ge 7$ and without degree two vertices, then $\mathrm {erb}(G) = L(G)$.