Facial rainbow edge-coloring of plane graphs (Q2413633)

In this note, the author introduces a facial rainbow edge-coloring of a loopless connected plane graph \(G\), which is an edge-coloring of \(G\) such that two distinct edges receive distinct colors if they lie on a common facial path of \(G\). The minimum number of colors in such a coloring is called the facial rainbow edge number of \(G\) and is denoted by \(\mathrm{erb}(G)\). Let \(G\) be a loopless connected plane graph and let \(L(G)\) be the length of the longest facial path of \(G\). The author proves that \(\mathrm{erb}(G)\leq \lfloor\frac{3}{2}(L(G) +1)\rfloor\) for all connected loopless plane graphs (this bound is tight). For the family of all 3-connected plane graphs, this bound is improved to \(L(G)+2\). For trees, \(\mathrm{erb}(G)\leq \lfloor\frac{3}{2}L(G)\rfloor\) holds (which is also tight), and if \(G\) is a tree with \(L(G) \geq 7\) and without vertices of degree two, then \(\mathrm{erb}(G) = L(G)\).