Facial rainbow edge-coloring of plane graphs (Q2413633)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Facial rainbow edge-coloring of plane graphs |
scientific article |
Statements
Facial rainbow edge-coloring of plane graphs (English)
0 references
14 September 2018
0 references
In this note, the author introduces a facial rainbow edge-coloring of a loopless connected plane graph \(G\), which is an edge-coloring of \(G\) such that two distinct edges receive distinct colors if they lie on a common facial path of \(G\). The minimum number of colors in such a coloring is called the facial rainbow edge number of \(G\) and is denoted by \(\mathrm{erb}(G)\). Let \(G\) be a loopless connected plane graph and let \(L(G)\) be the length of the longest facial path of \(G\). The author proves that \(\mathrm{erb}(G)\leq \lfloor\frac{3}{2}(L(G) +1)\rfloor\) for all connected loopless plane graphs (this bound is tight). For the family of all 3-connected plane graphs, this bound is improved to \(L(G)+2\). For trees, \(\mathrm{erb}(G)\leq \lfloor\frac{3}{2}L(G)\rfloor\) holds (which is also tight), and if \(G\) is a tree with \(L(G) \geq 7\) and without vertices of degree two, then \(\mathrm{erb}(G) = L(G)\).
0 references
cyclic coloring
0 references
rainbow coloring
0 references
plane graphs
0 references