Acyclic Colorings of Planar Graphs.
Abstract
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)
Document Details
- Document Type
- Technical Report
- Publication Date
- Aug 01, 1972
- Accession Number
- AD0747662
Entities
People
- Branko Gruenbaum
Organizations
- University of Washington