Discrete Mathematics & Theoretical Computer Science (Jan 2014)

Strong parity vertex coloring of plane graphs

  • Tomas Kaiser,
  • Ondrej Rucky,
  • Matej Stehlik,
  • Riste Skrekovski

DOI
https://doi.org/10.46298/dmtcs.640
Journal volume & issue
Vol. Vol. 16 no. 1

Abstract

Read online

A strong parity vertex coloring of a 2-connected plane graph is a coloring of the vertices such that every face is incident with zero or an odd number of vertices of each color. We prove that every 2-connected loopless plane graph has a strong parity vertex coloring with 97 colors. Moreover the coloring we construct is proper. This proves a conjecture of Czap and Jendrol' [Discuss. Math. Graph Theory 29 (2009), pp. 521-543.]. We also provide examples showing that eight colors may be necessary (ten when restricted to proper colorings).

Keywords