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{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.