- Tytuł:
- Facial Rainbow Coloring of Plane Graphs
- Autorzy:
-
Jendroľ, Stanislav
Kekeňáková, Lucia - Powiązania:
- https://bibliotekanauki.pl/articles/31343192.pdf
- Data publikacji:
- 2019-11-01
- Wydawca:
- Uniwersytet Zielonogórski. Wydział Matematyki, Informatyki i Ekonometrii
- Tematy:
-
cyclic coloring
rainbow coloring
plane graphs - Opis:
- A vertex coloring of a plane graph $G$ is a facial rainbow coloring if any two vertices of $G$ connected by a facial path have distinct colors. The facial rainbow number of a plane graph $G$, denoted by $ rb(G) $, is the minimum number of colors that are necessary in any facial rainbow coloring of $G$. Let $L(G)$ denote the order of a longest facial path in $G$. In the present note we prove that $ rb(T) \le \floor{ 3/2 L(T) } $ for any tree $T$ and $rb(G) \le \ceil{ 5/3 L(G) } $ for arbitrary simple graph $G$. The upper bound for trees is tight. For any simple 3-connected plane graph $G$ we have $ rb(G) \le L(G) + 5 $.
- Źródło:
-
Discussiones Mathematicae Graph Theory; 2019, 39, 4; 889-897
2083-5892 - Pojawia się w:
- Discussiones Mathematicae Graph Theory
- Dostawca treści:
- Biblioteka Nauki
Artykuł