Tomas Kaiser ; Ondrej Rucky ; Matej Stehlik ; Riste Skrekovski - Strong parity vertex coloring of plane graphs

dmtcs:640 - Discrete Mathematics & Theoretical Computer Science, January 1, 2014, Vol. 16 no. 1 - https://doi.org/10.46298/dmtcs.640
Strong parity vertex coloring of plane graphsArticle

Authors: Tomas Kaiser 1; Ondrej Rucky 1; Matej Stehlik 2; Riste Skrekovski

  • 1 department of mathematics and institute of computer science
  • 2 Optimisation Combinatoire

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).


Volume: Vol. 16 no. 1
Published on: January 1, 2014
Imported on: March 26, 2015
Keywords: [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]

Consultation statistics

This page has been seen 393 times.
This article's PDF has been downloaded 325 times.