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)
展开▼
