In
graph theory
In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...
, an acyclic coloring is a (proper)
vertex coloring in which every 2-chromatic subgraph is
acyclic. The acyclic chromatic number of a
graph
Graph may refer to:
Mathematics
*Graph (discrete mathematics), a structure made of vertices and edges
**Graph theory, the study of such graphs and their properties
*Graph (topology), a topological space resembling a graph in the sense of discret ...
is the fewest colors needed in any acyclic coloring of .
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.
* A(''G'') ≤ 5 if Δ(''G'') = 4.
* A(''G'') ≤ 7 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 A(''G'') ≤ 5 if ''G'' is planar graph.
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
A forest is an ecosystem characterized by a dense community of trees. Hundreds of definitions of forest are used throughout the world, incorporating factors such as tree density, tree height, land use, legal standing, and ecological functio ...
.
Algorithms and complexity
It is
NP-complete
In computational complexity theory, NP-complete problems are the hardest of the problems to which ''solutions'' can be verified ''quickly''.
Somewhat more precisely, a problem is NP-complete when:
# It is a decision problem, meaning that for any ...
to determine whether A(''G'') ≤ 3.
showed that the decision variant of the problem is NP-complete even when ''G'' is a
bipartite graph
In the mathematics, mathematical field of graph theory, a bipartite graph (or bigraph) is a Graph (discrete mathematics), graph whose vertex (graph theory), vertices can be divided into two disjoint sets, disjoint and Independent set (graph theo ...
.
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 .
See also
*
Star coloring
References
*.
*
*
*.
*.
*.
*.
*.
*.
*.
*
*
*
External links
Star colorings and acyclic colorings (1973) present at th
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.
{{DEFAULTSORT:Acyclic Coloring
Graph coloring