@Article{Czap2020,
author = "Czap, Július",
title = "Facial rainbow edge-coloring of simple 3-connected plane graphs",
journal = "Opuscula Math.",
year = "2020",
volume = "40",
number = "4",
pages = "475--482",
doi = "https://doi.org/10.7494/OpMath.2020.40.4.475",
url = "https://doi.org/10.7494/OpMath.2020.40.4.475",
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.",
keywords = "plane graph, facial path, edge-coloring",
issn = "1232-9274"
}