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 journalArticle

12 Scopus citations

Abstract

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
Volume42
Issue number3
DOIs
StatePublished - Jul 1 2009
Externally publishedYes

All Science Journal Classification (ASJC) codes

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

Keywords

  • Graph coloring
  • Guarding problems
  • Planar graphs

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. (2009). Polychromatic colorings of plane graphs. Discrete and Computational Geometry, 42(3), 421-442. https://doi.org/10.1007/s00454-009-9171-5