Facial parity edge coloring of outerplane graphs - Czap, Július (Ars mathematica contemporanea, 2012)
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.
Keywords: barvanje povezav; edge coloring; facial walk; graph theory; plane graph; ravninski graf; teorija grafov