@inproceedings{5f1b24537ca14345a697101fe60625e2,
title = "Polychromatic colorings of plane graphs",
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.",
keywords = "Algorithms, Theory",
author = "Noga Alon and Robert Berke and Kevin Buchin and Maike Buchin and P{\'e}ter Csorba and Saswata Shannigrahi and Bettina Speckmann and Philipp Zumstein",
year = "2008",
doi = "10.1145/1377676.1377734",
language = "English (US)",
isbn = "9781605580715",
series = "Proceedings of the Annual Symposium on Computational Geometry",
publisher = "Association for Computing Machinery",
pages = "338--345",
booktitle = "Proceedings of the 24th Annual Symposium on Computational Geometry 2008, SCG'08",
note = "24th Annual Symposium on Computational Geometry, SCG'08 ; Conference date: 09-06-2008 Through 11-06-2008",
}