Acyclic Colorings of Planar Graphs.
WASHINGTON UNIV SEATTLE DEPT OF MATHEMATICS
Pagination or Media Count:
Coloring problems of a new type are studied in a setting that combines coloring features and facts usually covered by the term arboricity. More precisely, a k-coloring of a graph G that is, a partition of the vertices of G into k pairwise disjoint colors so that adjacent vertices have different colors is called acyclic provided the subgraph spanned by vertices of any two colors is acyclic a forest. It is shown that every planar graph has an acyclic 9-coloring, and other results are given which extend and strengthen theorems obtained by Chartrand, Kronk, Wall, and Stein. Author
- Theoretical Mathematics