Facial parity edge coloring of outerplane graphs

Július Czap

Abstract


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


plane graph; facial walk; edge coloring

Full Text:

PDF ABSTRACTS (EN/SI)


DOI: https://doi.org/10.26493/1855-3974.228.ee8

ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications