@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",

}