Facial parity edge coloring of outerplane graphs
A facial parity edge coloring of a 2-edge-connected plane graph is such an edge coloring in which no two face-adjacent edges (consecutive edges of a facial walk of some face) receive the same color, in addition, for each face f and each color c, either no edge or an odd number of edges incident with f is colored with c. It is known that any 2-edge-connected plane graph has a facial parity edge coloring with at most 92 colors. In this paper we prove that any 2-edge-connected outerplane graph has a facial parity edge coloring with at most 15 colors. If a 2-edge-connected outerplane graph does not contain any inner edge, then 10 colors are sufficient. Moreover, this bound is tight.
plane graph; facial walk; edge coloring