Opuscula Math. 40, no. 4 (2020), 475-482
https://doi.org/10.7494/OpMath.2020.40.4.475

Opuscula Mathematica

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

Július Czap

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.

Mathematics Subject Classification: 05C10, 05C15.

Full text (pdf)

• Július Czap
• https://orcid.org/0000-0002-9933-5884
• Technical University of Košice, Faculty of Economics, Department of Applied Mathematics and Business Informatics, Němcovej 32, 040 01 Košice, Slovakia
• Communicated by Adam Paweł Wojda.
• Revised: .
• Accepted: 2020-04-26.
• Published online: 2020-07-09.