Added to Favorites

Related Searches

Nearby Words

In graph theory, an acyclic coloring is a (proper) vertex coloring in which every 2-chromatic subgraph is acyclic. The acyclic chromatic number A(G) of a graph G is the least number of colors needed in any acyclic coloring of G.

Some properties of A(G):

- A(G) ≤ 2 if and only if G is acyclic.
- A(G) ≤ 4 if Δ(G) = 3, where Δ(G) is the maximum degree of G. (Grünbaum 1973)
- A(G) ≤ 5 if Δ(G) = 4. (Burstein 1979)
- It is NP-complete to determine whether A(G) ≤ 3. (Kostochka 1978)

A milestone in the study of acyclic coloring is the following affirmative answer to a conjecture of Grünbaum:

Theorem. (Borodin 1979)

- A(G) ≤ 5 if G is planar graph.

Grünbaum (1973) introduced acyclic coloring and acyclic chromatic number, and conjectured the result in the above theorem. Borodin's proof involved several years of painstaking inspection of 450 reducible configurations. One consequence of this theorem is that every planar graph can be decomposed into an independent set and two forests. (Stein 1970, 1971)

Acyclic coloring is often associated with graphs embedded on non-plane surfaces.

- Borodin, O. V. (1979). On acyclic colorings of planar graphs. Discrete Math. 25, 211–236.
- Burstein, M. I. (1979). Every 4-valent graph has an acyclic 5-coloring (in Russian). Soobšč. Akad. Nauk Gruzin. SSR 93, 21–24.
- Grünbaum, B. (1973). Acyclic colorings of planar graphs. Israel J. Math. 14, 390–408.
- Jensen, Tommy R.; Toft, Bjarne (1995). Graph coloring problems. New York: Wiley-Interscience. ISBN 0-471-02865-7.
- Kostochka, A. V. (1978). Upper bounds of chromatic functions of graphs (in Russian). Doctoral thesis, Novosibirsk.
- Stein, S. K. (1970). B-sets and coloring problems. Bull. Amer. Math. Soc. 76, 805–806.
- Stein, S. K. (1971). B-sets and planar maps. Pacific J. Math. 37(1), 217–224.

Wikipedia, the free encyclopedia © 2001-2006 Wikipedia contributors (Disclaimer)

This article is licensed under the GNU Free Documentation License.

Last updated on Tuesday July 17, 2007 at 06:12:26 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

This article is licensed under the GNU Free Documentation License.

Last updated on Tuesday July 17, 2007 at 06:12:26 PDT (GMT -0700)

View this article at Wikipedia.org - Edit this article at Wikipedia.org - Donate to the Wikimedia Foundation

Copyright © 2015 Dictionary.com, LLC. All rights reserved.