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

10 Scopus citations


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
Number of pages8
ISBN (Print)9781605580715
StatePublished - 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


Other24th Annual Symposium on Computational Geometry, SCG'08
Country/TerritoryUnited States
CityCollege Park, MD

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Geometry and Topology
  • Computational Mathematics


  • Algorithms
  • Theory


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

Cite this