Strong parity vertex coloring of plane graphs
Tomáš Kaiser, Ondřej Rucký, Matěj Stehlík, Riste Škrekovski
Abstract
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 13;543.]. We also provide examples showing that eight colors
may be necessary (ten when restricted to proper colorings).
Full Text: PDF PostScript