Accession Number : AD0747662

Title :   Acyclic Colorings of Planar Graphs.

Descriptive Note : Technical rept.,

Corporate Author : WASHINGTON UNIV SEATTLE DEPT OF MATHEMATICS

Personal Author(s) : Gruenbaum,Branko

Report Date : AUG 1972

Pagination or Media Count : 27

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)

Descriptors :   (*GRAPHICS, COLORING), SET THEORY, THEOREMS

Subject Categories : Theoretical Mathematics

Distribution Statement : APPROVED FOR PUBLIC RELEASE