Acyclically 3-colorable planar graphs |
| |
Authors: | Patrizio Angelini Fabrizio Frati |
| |
Institution: | 1. Dipartimento di Informatica e Automazione, Universit?? Roma Tre, Rome, Italy
|
| |
Abstract: | In this paper we study the acyclic 3-colorability of some subclasses of planar graphs. First, we show that there exist infinite classes of cubic planar graphs that are not acyclically 3-colorable. Then, we show that every planar graph has a subdivision with one vertex per edge that is acyclically 3-colorable and provide a linear-time coloring algorithm. Finally, we characterize the series-parallel graphs for which every 3-coloring is acyclic and provide a linear-time recognition algorithm for such graphs. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|