Opuscula Math. 38, no. 6 (2018), 819-827
https://doi.org/10.7494/OpMath.2018.38.6.819
Opuscula Mathematica
Zig-zag facial total-coloring of plane graphs
Július Czap
Stanislav Jendroľ
Margit Voigt
Abstract. In this paper we introduce the concept of zig-zag facial total-coloring of plane graphs. We obtain lower and upper bounds for the minimum number of colors which is necessary for such a coloring. Moreover, we give several sharpness examples and formulate some open problems.
Keywords: plane graph, facial coloring, total-coloring, zig-zag coloring.
Mathematics Subject Classification: 05C10, 05C15.
- K. Appel, W. Haken, Every planar map is four colorable, Bull. Amer. Math. Soc. 82 (1976), 711-712.
- J.A. Bondy, U.S.R. Murty, Graph Theory, Springer, 2008.
- R.L. Brooks, On colouring the nodes of a network, Proc. Cambridge Philosophical Society, Math. Phys. Sci. 37 (1941), 194-197.
- J. Czap, S. Jendroľ, Facially-constrained colorings of plane graphs: A survey, Discrete Math. 340 (2017), 2691-2703.
- J. Czap, P. Šugerek, Facial total-coloring of bipartite plane graphs, Int. J. Pure Appl. Math. 115 (2017), 115-121.
- I. Fabrici, S. Jendroľ, M. Vrbjarová, Facial entire colouring of plane graphs, Discrete Math. 339 (2016), 626-631.
- I. Fabrici, S. Jendroľ, M. Voigt, Facial list colourings of plane graphs, Discrete Math. 339 (2016), 2826-2831.
- 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.
- S. Kitaev, Patterns in permutations and words, Springer, 2011.
- T.L. Saaty, P.C. Kainen, The Four-Color Problem, Assaults and Conquest, McGraw-Hill, 1977.
- P.G. Tait, Remarks on the colouring of maps, Proc. Roy. Soc. Edinburgh 10 (1880), 729.
- Július Czap
- Technical University of Košice, Department of Applied Mathematics and Business Informatics, Faculty of Economics, Němcovej 32, 04001 Košice, Slovakia
- Stanislav Jendroľ
- P.J. Šafárik University, Institute of Mathematics, Jesenná 5, 04001 Košice, Slovakia
- Margit Voigt
- University of Applied Sciences Dresden, Faculty of Informatics and Mathematics, Friedrich-List-Platz 1, 01069 Dresden, Germany
- Communicated by Adam Paweł Wojda.
- Received: 2018-01-24.
- Revised: 2018-02-13.
- Accepted: 2018-02-15.
- Published online: 2018-07-05.
