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

[摘要] 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.

[学科分类] 环境科学（综合）

[关键词] plane graph;facial path;edge-coloring.