Acyclic coloring
In graph theory, an acyclic coloring is a (proper) vertex coloring in which every 2-chromatic subgraph is acyclic. The acyclic chromatic number Template:Math of a graph Template:Mvar is the fewest colors needed in any acyclic coloring of Template:Mvar.
Acyclic coloring is often associated with graphs embedded on non-plane surfaces.
Upper bounds
A(G) ≤ 2 if and only if G is acyclic.
Bounds on A(G) in terms of Δ(G), the maximum degree of G, include the following:
- A(G) ≤ 4 if Δ(G) = 3. Template:Harv
- A(G) ≤ 5 if Δ(G) = 4. Template:Harv
- A(G) ≤ 7 if Δ(G) = 5. Template:Harv
- A(G) ≤ 12 if Δ(G) = 6. Template:Harv
A milestone in the study of acyclic coloring is the following affirmative answer to a conjecture of Grünbaum:
- Theorem Template:Harv A(G) ≤ 5 if G is planar graph.
Template:Harvtxt 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 induced forests. Template:Harvs
Algorithms and complexity
It is NP-complete to determine whether A(G) ≤ 3. Template:Harv
Template:Harvtxt showed that the decision variant of the problem is NP-complete even when G is a bipartite graph.
Template:Harvtxt demonstrated that every proper vertex coloring of a chordal graph is also an acyclic coloring. Since chordal graphs can be optimally colored in O(n + m) time, the same is also true for acyclic coloring on that class of graphs.
A linear-time algorithm to acyclically color a graph of maximum degree ≤ 3 using 4 colors or fewer was given by Template:Harvtxt.
See also
References
- Template:Citation.
- Template:Citation
- Template:Citation
- Template:Citation.
- Template:Citation.
- Template:Citation.
- Template:Citation.
- Template:Citation.
- Template:Citation.
- Template:Citation.
- Template:Citation
- Template:Citation
- Template:Citation
External links
- Star colorings and acyclic colorings (1973), present at the Research Experiences for Graduate Students (REGS) at the University of Illinois, 2008.
- Acyclic Coloring of Graphs of Maximum Degree ∆, talk slides presented by G. Fertin and A. Raspaud at EUROCOMB 05, Berlin, 2005.