Acyclic colorings of planar graphs |
| |
Authors: | Branko Grünbaum |
| |
Institution: | (1) University of Washington, Seattle, Washington, U.S.A. |
| |
Abstract: | A coloring of the vertices of a graph byk colors is called acyclic provided that no circuit is bichromatic. We prove that every planar graph has an acyclic coloring
with nine colors, and conjecture that five colors are sufficient. Other results on related types of colorings are also obtained;
some of them generalize known facts about “point-arboricity”.
Research supported in part by the Office of Naval Research under Grant N00014-67-A-0103-0003. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|