Odd facial colorings of acyclic plane graphs

Július Czap, Peter Šugerek


Let G be a connected plane graph with vertex set V and edge set E. For X ∈ {V, E, V ∪ E}, two elements of X are facially adjacent in G if they are incident elements, adjacent vertices, or facially adjacent edges (edges that are consecutive on the boundary walk of a face of G). A coloring of G is facial with respect to X if there is a coloring of elements of X such that facially adjacent elements of X receive different colors. A facial 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 paper we investigate odd facial colorings of trees. The main results of this paper are the following: (i) Every tree admits an odd facial vertex-coloring with at most 4 colors; (ii) Only one tree needs 6 colors, the other trees admit an odd facial edge-coloring with at most 5 colors; and (iii) Every tree admits an odd facial total-coloring with at most 5 colors. Moreover, all these bounds are tight.


facial coloring, odd facial coloring, plane graph

Full Text:


DOI: http://dx.doi.org/10.5614/ejgta.2021.9.2.8


T. Bálint and J. Czap, Facial parity 9-edge-coloring of outerplane graphs, Graphs Combin. 31 (2015), 1177–1187.

J.A. Bondy and U.S.R. Murty, Graph Theory, Springer, 2008.

J. Czap, Parity vertex coloring of outerplane graphs, Discrete Math. 311 (2011), 2570–2573.

J. Czap, S. Jendrol’, F. Kardoš. and R. Soták, Facial parity edge colouring of plane pseudographs, Discrete Math. 312 (2012), 2735–2740.

J. Czap, S. Jendrol’ and M. Voigt, Parity vertex colouring of plane graphs, Discrete Math. 311 (2011), 512–520.

I. Fabrici, S. Jendrol’, and M. Vrbjarová, Facial entire colouring of plane graphs, Discrete Math. 339 (2016), 626–631.

J. Czap and P. Šugerek, Facial total-coloring of bipartite plane graphs, Int. J. Pure Appl. Math. 115 (2017), 115–121.

J.L. Gross and T.W. Tucker, Topological Graph Theory, Dover Publications, 2001.

T. Kaiser, O. Rucký, M. Stehlík, and R. Škrekovski, Strong parity vertex coloring of plane graphs, Discrete Math. Theor. Comput. Sci. 16 (2014), 143–158.

H. Lu and Y. Lin, Note on parity factors of regular graphs, Electron. J. Graph Theory Appl. 1 (1) (2013), 50–55.

B. Lužar and R. Škrekovski, Improved bound on facial parity edge coloring, Discrete Math. 313 (2013), 2218–2222.

T.L. Saaty and P.C. Kainen, The Four Color Problem: Assaults and Conquest, McGraw-Hill, New York, 1977.

P.G. Tait, Remarks on the colouring of maps, Proc. Roy. Soc. Edinburgh 10 (1880), 729.

W. Wang, S. Finbow and P. Wang, An improved bound on parity vertex colourings of outerplane graphs, Discrete Math. 312 (2012), 2782–2787.


  • There are currently no refbacks.

ISSN: 2338-2287

Creative Commons License
This work is licensed under a Creative Commons Attribution-ShareAlike 4.0 International License.

View EJGTA Stats