Strong parity vertex coloring of plane graphs
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 colo...
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2014-01-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/640/pdf |
| _version_ | 1827323802914127872 |
|---|---|
| author | Tomas Kaiser Ondrej Rucky Matej Stehlik Riste Skrekovski |
| author_facet | Tomas Kaiser Ondrej Rucky Matej Stehlik Riste Skrekovski |
| author_sort | Tomas Kaiser |
| collection | DOAJ |
| description | 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). |
| first_indexed | 2024-04-25T01:58:25Z |
| format | Article |
| id | doaj.art-455f5257aca54a47963e5bdf05d59bfd |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T01:58:25Z |
| publishDate | 2014-01-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-455f5257aca54a47963e5bdf05d59bfd2024-03-07T15:27:46ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502014-01-01Vol. 16 no. 110.46298/dmtcs.640640Strong parity vertex coloring of plane graphsTomas Kaiser0Ondrej Rucky1Matej Stehlik2Riste Skrekovskidepartment of mathematics and institute of computer sciencedepartment of mathematics and institute of computer scienceOptimisation CombinatoireA 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).https://dmtcs.episciences.org/640/pdf[info.info-dm] computer science [cs]/discrete mathematics [cs.dm] |
| spellingShingle | Tomas Kaiser Ondrej Rucky Matej Stehlik Riste Skrekovski Strong parity vertex coloring of plane graphs Discrete Mathematics & Theoretical Computer Science [info.info-dm] computer science [cs]/discrete mathematics [cs.dm] |
| title | Strong parity vertex coloring of plane graphs |
| title_full | Strong parity vertex coloring of plane graphs |
| title_fullStr | Strong parity vertex coloring of plane graphs |
| title_full_unstemmed | Strong parity vertex coloring of plane graphs |
| title_short | Strong parity vertex coloring of plane graphs |
| title_sort | strong parity vertex coloring of plane graphs |
| topic | [info.info-dm] computer science [cs]/discrete mathematics [cs.dm] |
| url | https://dmtcs.episciences.org/640/pdf |
| work_keys_str_mv | AT tomaskaiser strongparityvertexcoloringofplanegraphs AT ondrejrucky strongparityvertexcoloringofplanegraphs AT matejstehlik strongparityvertexcoloringofplanegraphs AT risteskrekovski strongparityvertexcoloringofplanegraphs |