Facial rainbow edge-coloring of simple 3-connected plane graphs

Abstract

A facial rainbow edge-coloring of a plane graph $G$ is an edge-coloring such that any two edges receive distinct colors if they lie on a common facial path of $G$. The minimum number of colors used in such a coloring is denoted by $\text{erb}(G)$. Trivially, $\text{erb}(G) \geq \text{L}(G)+1$ holds for every plane graph without cut-vertices, where $\text{L}(G)$ denotes the length of a longest facial path in $G$. Jendroľ in 2018 proved that every simple $3$-connected plane graph admits a facial rainbow edge-coloring with at most $\text{L}(G)+2$ colors, moreover, this bound is tight for $\text{L}(G)=3$. He also proved that $\text{erb}(G)=\text{L}(G)+1$ for $\text{L}(G)\not\in\{3,4,5\}$. He posed the following conjecture: There is a simple $3$-connected plane graph $G$ with $\text{L}(G)=4$ and $\text{erb}(G)=\text{L}(G)+2$. In this note we answer the conjecture in the affirmative.