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/

[1] O. Amini, L. Esperet and J. van den Heuvel, A unified approach to distance-two colouring of planar graphs, in: Proc. SODA 2009 273–282. doi:10.1137/1.9781611973068.31

[2] K. Appel and W. Haken, Every planar graph is four colorable, Part I : Discharging, Illinois J. Math. 21 (1977) 429–490.

[3] K. Appel and W. Haken, Every planar graph is four colorable, Part II : Reducibility, Illinois J. Math. 21 (1977) 491–567.

[4] J. Azarija, R. Erman, D. Kráľ, M. Krnc and L. Stacho, Cyclic colorings of plane graphs with independent faces, European J. Combin. 33 (2012) 294–301. doi:10.1016/j.ejc.2011.09.011

[5] O.V. Borodin, Solution of Ringel’s problems on vertex-face coloring of plane graphs and coloring of 1 -planar graphs, Met. Diskret. Anal. 41 (1984) 12–26.

[6] O.V. Borodin, Cyclic coloring of plane graphs, Discrete Math. 100 (1992) 281–289. doi:10.1016/0012-365X(92)90647-X

[7] O.V. Borodin, A new proof of the 6 color theorem, J. Graph Theory 19 (1995) 507–521. doi:10.1002/jgt.3190190406

[8] O.V. Borodin, Colorings of plane graphs: A survey, Discrete Math. 313 (2013) 517–539. doi:10.1016/j.disc.2012.11.011

[9] O.V. Borodin, D.P. Sanders and Y. Zhao, On cyclic colorings and their generalizations, Discrete Math. 203 (1999) 23–40. doi:10.1016/S0012-365X(99)00018-7

[10] J. Czap and S. Jendroľ, Facially-constrained colorings of plane graphs: A survey, Discrete Math. 340 (2017) 2691–2730. doi:10.1016/j.disc.2016.07.026

[11] Z. Dvořák, M. Hebdige, F. Hlásek and D. Kráľ, Cyclic coloring of plane graphs with maximum face size 16 and 17. arXiv:1603.06722v2[math.CO]

[12] Z. Dvořák, D. Kráľ and R. Škrekovski, Non-rainbow coloring of 3 -, 4 -, and 5 - connected plane graphs, J. Graph Theory 63 (2010) 129–145. doi:10.1002/jgt.20414

[13] H. Enomoto and M. Horňák, A general upper bound for the cyclic chromatic number of 3 -connected plane graphs, J. Graph Theory 62 (2009) 1–25. doi:10.1002/jgt.20383

[14] H. Enomoto, M. Horňák and S. Jendroľ, Cyclic chromatic number of 3 -connected plane graphs, SIAM J. Discrete Math. 14 (2001) 121–137. doi:10.1137/S0895480198346150

[15] F. Fujie-Okamoto, K. Kolasinski, J.W. Lin and P. Zhang, Vertex rainbow colorings of graphs, Discuss. Math. Graph Theory 32 (2012) 63–68. doi:10.7151/dmgt.1586

[16] J.L. Gross and T.W. Tucker, Topological Graph Theory (Dover Publications, 2001).

[17] F. Havet, J.-S. Sereni and R. Škrekovski, 3 -facial coloring of plane graphs, SIAM J. Discrete Math 22 (2008) 231–247. doi:10.1137/060664124

[18] M. Hebdige and D. Kráľ, Third case of the cyclic coloring conjecture. arxiv.org/pdf/1501.06624.pdf

[19] M. Horňák and S. Jendroľ, On a conjecture by Plummer and Toft, J. Graph Theory 30 (1999) 177–189. doi:10.1002/(SICI)1097-0118(199903)30:3<177::AID-JGT3>3.0.CO;2-K

[20] M. Horňák and J. Zlámalová, Another step towards proving a conjecture by Plummer and Toft, Discrete Math. 310 (2010) 442–452. doi:10.1016/j.disc.2009.03.016

[21] S. Jendroľ and L. Kekeňáková, Facial rainbow colorings of trees, Australas. J. Combin. 69 (2017) 358–367.

[22] T.R. Jensen and B. Toft, Graph Coloring Problems (Wiley, New York, 1995).

[23] Z. Jin, Y. Sun and J. Tu, Rainbow total-coloring of complementary graphs and Erdős-Gallai type problem for the rainbow total connection number, Discuss. Math. Graph Theory 38 (2018) 1023–1036. doi:10.7151/dmgt.2056

[24] X. Li, Y. Shi and Y. Sun, Rainbow connection of a graph; a survey, Graphs Combin. 29 (2013) 1–38. doi:10.1007/s00373-012-1243-2

[25] O. Ore and M.D. Plummer, Cyclic coloration of plane graphs, in: W.T. Tutte (Ed.), Recent Progress in Combinatorics (Proceedings of the Third Waterloo Conference on Combinatorics, May 1968) (Academic Press, 1969).

[26] M.D. Plummer and B. Toft, Cyclic coloration of 3 -polytopes, J. Graph Theory 11 (1987) 507–515. doi:10.1002/jgt.3190110407

[27] G. Ringel, Ein Sechsfarbenproblem auf der Kugel, Abh. Math. Semin. Univ. Hambg. 29 (1965) 107–117. doi:10.1007/BF02996313

[28] N. Robertson, D.P. Sanders, P.D. Seymour and R. Thomas, The four-colour theorem, J. Combin. Theory Ser. B 70 (1999) 2–44. doi:10.1006/jctb.1997.1750

[29] D.P. Sanders and Y. Zhao, A new bound on the cyclic chromatic number, J. Combin. Theory Ser. B 83 (2001) 102–111. doi:10.1006/jctb.2001.2046

[30] D. West, Introduction to Graph Theory, Second Edition (Prentice Hall, Upper Saddle River, 2001).