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

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

Title of host publication | Proceedings of the 24th Annual Symposium on Computational Geometry 2008, SCG'08 |

Publisher | Association for Computing Machinery |

Pages | 338-345 |

Number of pages | 8 |

ISBN (Print) | 9781605580715 |

DOIs | |

State | Published - Jan 1 2008 |

Externally published | Yes |

Event | 24th Annual Symposium on Computational Geometry, SCG'08 - College Park, MD, United States Duration: Jun 9 2008 → Jun 11 2008 |

### Publication series

Name | Proceedings of the Annual Symposium on Computational Geometry |
---|

### Other

Other | 24th Annual Symposium on Computational Geometry, SCG'08 |
---|---|

Country | United States |

City | College Park, MD |

Period | 6/9/08 → 6/11/08 |

### All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Geometry and Topology
- Computational Mathematics

## Fingerprint Dive into the research topics of 'Polychromatic colorings of plane graphs'. Together they form a unique fingerprint.

## Cite this

*Proceedings of the 24th Annual Symposium on Computational Geometry 2008, SCG'08*(pp. 338-345). (Proceedings of the Annual Symposium on Computational Geometry). Association for Computing Machinery. https://doi.org/10.1145/1377676.1377734