A note on odd facial total-coloring of cacti

Document Type : Original paper

Author

Department of Applied Mathematics and Business Informatics, Faculty of Economics, Technical University of Kosice

Abstract

A facial total-coloring of a plane graph $G$ is a coloring of the vertices and edges such that no facially adjacent edges, no adjacent vertices, and no edge and its endvertices are assigned the same color. A facial total-coloring of $G$ is odd if for every face $f$ and every color $c$, either no element or an odd number of elements incident with $f$ is colored by $c$. In this note we prove that every cactus forest with an outerplane embedding admits an odd facial total-coloring with at most 16 colors. Moreover, this bound is tight.

Keywords

Main Subjects

References

[1] J. Czap, Odd facial total-coloring of unicyclic plane graphs, Discrete Math. Lett. 10 (2022), 56–59.
[2] J. Czap and S. Jendrol’, Facially-constrained colorings of plane graphs: A survey, Discrete Math. 340 (2017), no. 11, 2691–2703.
[3] J. Czap and S. Jendrol’, Facial colorings of plane graphs, J. Interconnect. Netw. 19 (2019), no. 1,
ID: 1940003.
[4] J. Czap and P. Šugerek, Odd facial colorings of acyclic plane graphs, Electron. J. Graph Theory Appl. 9 (2021), no. 2, 347–355.
[5] I. Fabrici, M. Horňák, and S. Rindošová, Facial unique-maximum edge and total coloring of plane graphs, Discrete Appl. Math. 291 (2021), 171–179.
[6] I. Fabrici, S. Jendrol’, and M. Voigt, Facial list colourings of plane graphs, Discrete Math. 339 (2016), no. 11, 2826–2831.
[7] I. Fabrici, S. Jendrol’, and M. Vrbjarová, Facial entire colouring of plane graphs, Discrete Math. 339 (2016), no. 2, 626–631.
Communications in Combinatorics and Optimization
Volume 8, Issue 3
September 2023
Pages 589-594

Files

Share

How to cite

Statistics