NoteParity vertex coloring of outerplane graphs

A proper vertex coloring of a 2-connected plane graph G is a parity vertex coloring if for each face f and each color c, the total number of vertices of color c incident with f is odd or zero. The minimum number of colors used in such a coloring of G is denoted by χp(G).In this paper we prove that χp(G)≤12 for every 2-connected outerplane graph G. We show that there is a 2-connected outerplane graph G such that χp(G)=10. If a 2-connected outerplane graph G is bipartite, then χp(G)≤8, moreover, this bound is best possible.

► The parity chromatic number of any 2-connected outerplane graph is at most 12. ► There is a 2-connected outerplane graph with parity chromatic number 10. ► The parity chromatic number of any 2-connected bipartite outerplane graph is at most 8.