Polychromatic colorings of plane graphs

Noga Alon, Robert Berke, Kevin Buchin, Maike Buchin, Péter Csorba, Saswata Shannigrahi, Bettina Speckmann, Philipp Zumstein

Research output: Chapter in Book/Report/Conference proceedingConference contribution

9 Scopus citations

Abstract

We show that the vertices of any plane graph in which every face is of size at least g can be colored by [(3g - 5)/4] colors so that every color appears in every face. This is nearly tight, as there are plane graphs that admit no vertex coloring of this type with more than [(3g + 1)/4J] colors. We further show that the problem of determining whether a plane graph admits a vertex coloring by 3 colors in which all colors appear in every face is A^P-complete even for graphs in which all faces are of size 3 or 4 only. If all faces are of size 3 this can be decided in polynomial time.

Original languageEnglish (US)
Title of host publicationProceedings of the 24th Annual Symposium on Computational Geometry 2008, SCG'08
PublisherAssociation for Computing Machinery
Pages338-345
Number of pages8
ISBN (Print)9781605580715
DOIs
StatePublished - Jan 1 2008
Externally publishedYes
Event24th Annual Symposium on Computational Geometry, SCG'08 - College Park, MD, United States
Duration: Jun 9 2008Jun 11 2008

Publication series

NameProceedings of the Annual Symposium on Computational Geometry

Other

Other24th Annual Symposium on Computational Geometry, SCG'08
CountryUnited States
CityCollege Park, MD
Period6/9/086/11/08

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Geometry and Topology
  • Computational Mathematics

Fingerprint Dive into the research topics of 'Polychromatic colorings of plane graphs'. Together they form a unique fingerprint.

  • Cite this

    Alon, N., Berke, R., Buchin, K., Buchin, M., Csorba, P., Shannigrahi, S., Speckmann, B., & Zumstein, P. (2008). Polychromatic colorings of plane graphs. In Proceedings of the 24th Annual Symposium on Computational Geometry 2008, SCG'08 (pp. 338-345). (Proceedings of the Annual Symposium on Computational Geometry). Association for Computing Machinery. https://doi.org/10.1145/1377676.1377734