Geodesic
Colorings of Plane Graphs Without Long Monochromatic Facial Paths
Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 3, pp. 801-808.

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

Let G be a plane graph. A facial path of G is a subpath of the boundary walk of a face of G. We prove that each plane graph admits a 3-coloring (a 2-coloring) such that every monochromatic facial path has at most 3 vertices (at most 4 vertices). These results are in a contrast with the results of Chartrand, Geller, Hedetniemi (1968) and Axenovich, Ueckerdt, Weiner (2017) which state that for any positive integer t there exists a 4-colorable (a 3-colorable) plane graph Gt such that in any its 3-coloring (2-coloring) there is a monochromatic path of length at least t. We also prove that every plane graph is 2-list-colorable in such a way that every monochromatic facial path has at most 4 vertices.
Keywords: plane graph, facial path, vertex-coloring 
@article{DMGT_2021_41_3_a6,
     author = {Czap, J\'ulius and Fabrici, Igor and Jendrol{\textquoteright}, Stanislav},
     title = {Colorings of {Plane} {Graphs} {Without} {Long} {Monochromatic} {Facial} {Paths}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {801--808},
     publisher = {mathdoc},
     volume = {41},
     number = {3},
     year = {2021},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2021_41_3_a6/}
}
TY  - JOUR
AU  - Czap, Július
AU  - Fabrici, Igor
AU  - Jendrol’, Stanislav
TI  - Colorings of Plane Graphs Without Long Monochromatic Facial Paths
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2021
SP  - 801
EP  - 808
VL  - 41
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2021_41_3_a6/
LA  - en
ID  - DMGT_2021_41_3_a6
ER  - 
%0 Journal Article
%A Czap, Július
%A Fabrici, Igor
%A Jendrol’, Stanislav
%T Colorings of Plane Graphs Without Long Monochromatic Facial Paths
%J Discussiones Mathematicae. Graph Theory
%D 2021
%P 801-808
%V 41
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2021_41_3_a6/
%G en
%F DMGT_2021_41_3_a6
Czap, Július; Fabrici, Igor; Jendrol’, Stanislav. Colorings of Plane Graphs Without Long Monochromatic Facial Paths. Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 3, pp. 801-808. http://geodesic.mathdoc.fr/item/DMGT_2021_41_3_a6/

[1] K. Appel and W. Haken, Every planar map is four colorable, Bull. Amer. Math. Soc. 82 (1976) 711–712. doi:10.1090/s0002-9904-1976-14122-5

[2] M. Axenovich, T. Ueckerdt and P. Weiner, Splitting planar graphs of girth 6 into two linear forests with short paths, J. Graph Theory 85 (2017) 601–618. doi:10.1002/jgt.22093

[3] J.A. Bondy and U.S.R. Murty, Graph Theory (Springer, 2008).

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

[5] O.V. Borodin, A. Kostochka and M. Yancey, On 1 -improper 2 -coloring of sparse graphs, Discrete Math. 313 (2013) 2638–2649. doi:10.1016/j.disc.2013.07.014

[6] H. Broersma, F.V. Fomin, J. Kratochvíl and G.J. Woeginger, Planar graph coloring avoiding monochromatic subgraphs: trees and paths make it difficult, Algorithmica 44 (2006) 343–361. doi:10.1007/s00453-005-1176-8

[7] G. Chartrand, D.P. Geller and S.T. Hedetniemi, A generalization of the chromatic number, Math. Proc. Cambridge Philos. Soc. 64 (1968) 265–271. doi:10.1017/s0305004100042808

[8] G. Chartrand, D.P. Geller and S. Hedetniemi, Graphs with forbidden subgraphs, J. Combin. Theory Ser. B 10 (1971) 12–41. doi:10.1016/0095-8956(71)90065-7

[9] L. Cowen, W. Goddard and C.E. Jesurum, Defective coloring revisited, J. Graph Theory 24 (1997) 205–219. doi:10.1002/(sici)1097-0118(199703)24:3〈205::aid-jgt2〉3.0.co;2-t

[10] J. Czap, S. Jendrol’ and J. Valiska, Worm colorings of planar graphs, Discuss. Math. Graph Theory 37 (2017) 353–368. doi:10.7151/dmgt.1921

[11] W. Goddard, Acyclic colorings of planar graphs, Discrete Math. 91 (1991) 91–94. doi:10.1016/0012-365x(91)90166-y

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

[13] H. Grötzsch, Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel, Wiss. Z. Martin-Luther-Universität, Halle-Wittenberg, Math.-Nat. Reihe 8 (1959) 109–120.

[14] L. Lovász, On decomposition of graphs, Studia Sci. Math. Hungar. 1 (1966) 237–238.

[15] K.S. Poh, On the linear vertex-arboricity of a planar graph, J. Graph Theory 14 (1990) 73–75. doi:10.1002/jgt.3190140108

[16] C. Thomassen, 2 -list-coloring planar graphs without monochromatic triangles, J. Combin. Theory Ser. B 98 (2008) 1337–1348. doi:10.1016/j.jctb.2008.02.006

[17] Y. Wang and L. Xu, Improper choosability of planar graphs without 4 -cycles, SIAM J. Discrete Math. 27 (2013) 2029–2037. doi:10.1137/120885140

[18] Y. Wang and J. Xu, Decomposing a planar graph without cycles of length 5 into a matching and a 3 -colorable graph, European J. Combin. 43 (2015) 98–123. doi:10.1016/j.ejc.2014.08.020