Odd facial colorings of acyclic plane graphs

Abstract

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.