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

Opuscula Mathematica

Július Czap¹ 

[1] Technical University of Košice, Faculty of Economics, Department of Applied Mathematics and Business Informatics, Němcovej 32, 040 01 Košice, Slovakia;

关键词: plane graph;    facial path;    edge-coloring;   

DOI  :  https://doi.org/10.7494/OpMath.2020.40.4.475

来源: DOAJ

【 摘 要 】

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.

【 授权许可】

Unknown