Accession Number:

AD0747662

Title:

Acyclic Colorings of Planar Graphs.

Descriptive Note:

Technical rept.,

Corporate Author:

WASHINGTON UNIV SEATTLE DEPT OF MATHEMATICS

Personal Author(s):

Report Date:

1972-08-01

Pagination or Media Count:

27.0

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

Subject Categories:

  • Theoretical Mathematics

Distribution Statement:

APPROVED FOR PUBLIC RELEASE