Strong parity vertex coloring of plane graphs

Graph Theory 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. More...

Full description

Saved in:
Bibliographic Details
Published in:Discrete mathematics and theoretical computer science 2014-01, Vol.16 no. 1 (Graph Theory), p.143-158
Main Authors: Kaiser, Tomas, Rucky, Ondrej, Stehlik, Matej, Škrekovski, Riste
Format: Article
Language:English
Subjects:
[info.info-dm] computer science [cs]/discrete mathematics [cs.dm]
Combinatorics
Computer Science
Discrete Mathematics
Graph theory
Graphs
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:Graph Theory 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).
ISSN:1365-8050
1462-7264
1365-8050
DOI:10.46298/dmtcs.1268