Polychromatic Colorings of Plane Graphs
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 for k = 2 and is NP-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, and for the others it is NP-complete.
graph coloring planar graphs guarding problems