Acyclic coloring - AbsoluteAstronomy.com

Graph theory

In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...

, an acyclic coloring is a (proper) vertex coloring

Graph coloring

In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices share the...

in which every 2-chromatic

Graph coloring

subgraph is acyclic

Glossary of graph theory

Graph theory is a growing area in mathematical research, and has a large specialized vocabulary. Some authors use the same word with different meanings. Some authors use different words to mean the same thing. This page attempts to keep up with current usage....

.
The acyclic chromatic number A(G) of a graph G is the least number of colors needed in any acyclic coloring of G.

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 the maximum degree

Glossary of graph theory

Δ(G) of G include the following:

A(G) ≤ 4 if Δ(G) = 3. (Grünbaum 1973)
A(G) ≤ 5 if Δ(G) = 4. (Burstein 1979)
A(G) ≤ 8 if Δ(G) = 5.
A(G) ≤ 12 if Δ(G) = 6.

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

Glossary of graph theory

and two forests

Glossary of graph theory

. (Stein 1970, 1971)

Algorithms and Complexity

It is NP-complete

NP-complete

In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...

to determine whether A(G) ≤ 3 (Kostochka 1978).
showed that the decision variant of the problem is NP-complete even when G is a bipartite graph.

demonstrated that every proper vertex coloring of a chordal graph

Chordal graph

In the mathematical area of graph theory, a graph is chordal if each of its cycles of four or more nodes has a chord, which is an edge joining two nodes that are not adjacent in the cycle. An equivalent definition is that any chordless cycles have at most three nodes...

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 .
describe a linear-time algorithm to acyclically color a graph of maximum degree ≤ 5 using 8 colors or fewer and also to color a graph of maximum degree ≤ 6 using 12 colors or fewer.

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.

The source of this article is wikipedia, the free encyclopedia. The text of this article is licensed under the GFDL.