Facial rainbow edge-coloring of plane graphs
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)\).
- 3-Facial Coloring of Plane Graphs
- A general upper bound for the cyclic chromatic number of 3-connected plane graphs
- A new bound on the cyclic chromatic number
- A Theorem on Coloring the Lines of a Network
- Another step towards proving a conjecture by Plummer and Toft
- Chromatic graph theory
- Colorings of plane graphs: a survey
- Cyclic chromatic number of 3-connected plane graphs
- Cyclic coloration of 3-polytopes
- Cyclic coloring of plane graphs
- Cyclic colorings of plane graphs with independent faces
- Facial rainbow colorings of trees
- Facially-constrained colorings of plane graphs: a survey
- scientific article; zbMATH DE number 3494450 (Why is no real title available?)
- scientific article; zbMATH DE number 1275149 (Why is no real title available?)
- scientific article; zbMATH DE number 7111892 (Why is no real title available?)
- scientific article; zbMATH DE number 3310750 (Why is no real title available?)
- Planar graphs of maximum degree seven are Class I
- Rainbow generalizations of Ramsey theory: A survey
- Third case of the cyclic coloring conjecture
- Topological graph theory.
- Facial \(L(2, 1)\)-edge-labelings of trees
- Facial packing vertex-coloring of subdivided plane graphs
- A survey on the cyclic coloring and its relaxations
- Facial rainbow coloring of plane graphs
- Facial parity edge colouring
- Facial rainbow edge-coloring of simple 3-connected plane graphs
- Rainbow faces in edge-colored plane graphs
- Facial rainbow colorings of trees
- Facial parity edge coloring of outerplane graphs
- Facial edge ranking of plane graphs
This page was built for publication: Facial rainbow edge-coloring of plane graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2413633)
