Geodesic
Facial Rainbow Coloring of Plane Graphs
Discussiones Mathematicae. Graph Theory, Tome 39 (2019) no. 4, pp. 889-897

Voir la notice de l'article provenant de la source Library of Science

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) ≤ 3/2 L(T) for any tree T and rb(G) ≤ 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) ≤ L(G) + 5.
Keywords: cyclic coloring, rainbow coloring, plane graphs 
@article{DMGT_2019_39_4_a9,
     author = {Jendro\v{l}, Stanislav and Keke\v{n}\'akov\'a, Lucia},
     title = {Facial {Rainbow} {Coloring} of {Plane} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {889--897},
     publisher = {mathdoc},
     volume = {39},
     number = {4},
     year = {2019},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2019_39_4_a9/}
}
TY  - JOUR
AU  - Jendroľ, Stanislav
AU  - Kekeňáková, Lucia
TI  - Facial Rainbow Coloring of Plane Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2019
SP  - 889
EP  - 897
VL  - 39
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2019_39_4_a9/
LA  - en
ID  - DMGT_2019_39_4_a9
ER  - 
%0 Journal Article
%A Jendroľ, Stanislav
%A Kekeňáková, Lucia
%T Facial Rainbow Coloring of Plane Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2019
%P 889-897
%V 39
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2019_39_4_a9/
%G en
%F DMGT_2019_39_4_a9
Jendroľ, Stanislav; Kekeňáková, Lucia. Facial Rainbow Coloring of Plane Graphs. Discussiones Mathematicae. Graph Theory, Tome 39 (2019) no. 4, pp. 889-897. http://geodesic.mathdoc.fr/item/DMGT_2019_39_4_a9/