Polychromatic colorings of plane graphs

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

Research output: Contribution to journalArticlepeer-review

18 Scopus citations


We show that the vertices of any plane graph in which every face is incident to at least g vertices 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 where all faces are incident to at least g vertices and that admit no vertex coloring of this type with more than ⌊(3g + 1)/4⌋ colors. We further show that the problem of determining whether a plane graph admits a vertex coloring by k colors in which all colors appear in every face is in P{script} for k = 2 and is N{script}P{script}-complete for k = 3,4. We refine this result for polychromatic 3-colorings restricted to 2-connected graphs which have face sizes from a prescribed (possibly infinite) set of integers. Thereby we find an almost complete characterization of these sets of integers (face sizes) for which the corresponding decision problem is in P{script} and for the others it is N{script}P{script}-complete.

Original languageEnglish (US)
Pages (from-to)421-442
Number of pages22
JournalDiscrete and Computational Geometry
Issue number3
StatePublished - 2009
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Geometry and Topology
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics


  • Graph coloring
  • Guarding problems
  • Planar graphs


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

Cite this