Article in press
Authors:
Stanislav Jendrol'
Institute of Mathematics, P. J. Šafárik University in Košice, Jesenná 5, SK-041 54 Košice
email: stanislav.jendrol@upjs.sk
Title:
On a 3-coloring of plane graphs without monochromatic facial 3-paths
PDFSource:
Discussiones Mathematicae Graph Theory
Received: 2024-10-01 , Revised: 2025-03-20 , Accepted: 2025-03-20 , Available online: 2025-04-07 , https://doi.org/10.7151/dmgt.2584
Abstract:
A facial path in a plane graph $G$ is a subpath of the boundary
walk of a face of $G$. The Four Color Theorem states that every plane graph
contains a proper vertex $4$-coloring in which each monochromatic path consists
of exactly one vertex. Czap, Fabrici, and Jendroľ in 2021 conjectured that
every plane graph $G$ admits an improper vertex 3-coloring in which every
monochromatic facial path in $G$ has at most two vertices. In this paper we
prove this conjecture. Our result is optimal.
Keywords:
plane graph, facial path, vertex-coloring
References:
- H.L. Abbott and B. Zhou, On small faces in $4$-critical graphs, Ars Combin. 32 (1991) 203–207.
- K. Appel and W. Haken, Every planar map is four colorable, Bull. Amer. Math. Soc. 82 (1976) 711–712.
https://doi.org/10.1090/S0002-9904-1976-14122-5 - J.A. Bondy and U.S.R. Murty, Graph Theory, Grad. Texts in Math. 244 (Springer-Verlag, London, 2008).
- O.V. Borodin, Coloring of plane graphs: A survey, Discrete Math. 313 (2013) 517–539.
https://doi.org/10.1016/j.disc.2012.11.011 - O.V. Borodin, A.N. Glebov and A. Raspaud, Planar graphs without triangles adjacent to cycles of length from $4$ to $7$ are $3$-colorable, Discrete Math. 310 (2010) 2584–2594.
https://doi.org/10.1016/j.disc.2010.03.021 - O.V. Borodin, A.N. Glebov, M. Montassier and A. Raspaud, Planar graphs without $5$- and $7$-cycles and without adjacent triangles are $3$-colorable, J. Combin. Theory Ser. B 99 (2009) 668–673.
https://doi.org/10.1016/j.jctb.2008.11.001 - 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.
https://doi.org/10.1007/s00453-005-1176-8 - G. Chartrand, D.P. Geller and S.T. Hedetniemi, A generalization of the chromatic number, Math. Proc. Cambridge Philos. Soc. 64 (1968) 265–271.
https://doi.org/10.1017/S0305004100042808 - V. Cohen-Addad, M. Hebdige, D. Kráľ, Z. Li and E. Salgado, Steinberg's conjecture is false, J. Combin. Theory Ser. B 122 (2017) 452–456
.
https://doi.org/10.1016/j.jctb.2016.07.006 - J. Czap, I. Fabrici and S. Jendroľ, Colorings of plane graphs without long monochromatic facial paths, Discuss. Math. Graph Theory 41 (2021) 801–808.
https://doi.org/https://doi.org/10.7151/dmgt.2319 - J. Czap, M. Horňák and S. Jendroľ, A survey on the cyclic coloring and its relaxations, Discuss. Math. Graph Theory 41 (2021) 5–38.
https://doi.org/10.7151/dmgt.2369 - W. Goddard, Acyclic colorings of planar graphs, Discrete Math. 91 (1991) 91–94.
https://doi.org/10.1016/0012-365X(91)90166-Y - H. Grötzsch, Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel, Wiss. Z. Martin-Luther-Univ., Halle-Wittenberg, Math.-Nat. Reihe 8 (1959) 109–120.
- H. Lebesgue, Quelques consequences simple de la formula d'Euler, J. Math. Pures Appl. 9 (1940) 27–43.
- K.S. Poh, On the linear vertex-arboricity of a planar graph, J. Graph Theory 14 (1990) 73–75.
https://doi.org/10.1002/jgt.3190140108 - D.P. Sanders and Y. Zhao, A note on the three color problem, Graphs Combin. 11 (1995) 91–94.
https://doi.org/10.1007/BF01787424 - R. Steinberg, The state of the three color problem, Ann. Discrete Math. 55 (1993) 211–248.
https://doi.org/10.1016/S0167-5060(08)70391-1 - L.J. Stockmeyer,, Planar $3$-colorability is polynomial complete, ACM SIGACT News 5(3) (1973) 19–25.
https://doi.org/10.1145/1008293.1008294
Close