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

Original language | English (US) |
---|---|

Pages (from-to) | 421-442 |

Number of pages | 22 |

Journal | Discrete and Computational Geometry |

Volume | 42 |

Issue number | 3 |

DOIs | |

State | Published - 2009 |

Externally published | Yes |

## All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Geometry and Topology
- Discrete Mathematics and Combinatorics
- Computational Theory and Mathematics

## Keywords

- Graph coloring
- Guarding problems
- Planar graphs