Polychromatic Colorings of Plane Graphs |
| |
Authors: | Noga Alon Robert Berke Kevin Buchin Maike Buchin Péter Csorba Saswata Shannigrahi Bettina Speckmann Philipp Zumstein |
| |
Institution: | (1) Tel Aviv University, Tel Aviv, Israel;(2) Tokyo Institute of Technology, Tokyo, Japan;(3) Universiteit Utrecht, Utrecht, The Netherlands;(4) TU Eindhoven, Eindhoven, The Netherlands;(5) Tata Inst. of Fund. Research, Mumbai, India;(6) ETH Zürich, Zürich, Switzerland |
| |
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 ℘ for k=2 and is
-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 ℘, and for the others it is
-complete.
Research of N. Alon was supported in part by the Israel Science Foundation, by a USA–Israeli BSF grant, and by the Hermann
Minkowski Minerva Center for Geometry at Tel Aviv University.
Research of R. Berke was supported in part by JSPS Global COE program “Computationism as a Foundation for the Sciences.”
Research of K. Buchin and M. Buchin was supported by the Netherlands’ Organisation for Scientific Research (NWO) under BRICKS/FOCUS
project no. 642.065.503.
Research of P. Csorba was supported by DIAMANT, an NWO mathematics cluster.
Research of B. Speckmann was supported by the Netherlands’ Organisation for Scientific Research (NWO) under project no. 639.022.707. |
| |
Keywords: | Graph coloring Planar graphs Guarding problems |
本文献已被 SpringerLink 等数据库收录! |
|