In
graph theory
In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...
, an acyclic coloring is a (proper)
vertex 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 o ...
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 discre ...
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
This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.
Symbols
A
B
...
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
Induce may refer to:
* Induced consumption
* Induced innovation
* Induced character
* Induced coma
* Induced menopause
* Induced metric
* Induced path
* Induced topology
* Induce (musician), American musician
See also
* Inducement (disambiguation ...
forests
A forest is an area of land dominated by 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 function. The United Nations' ...
.
Algorithms and complexity
It is
NP-complete
In computational complexity theory, a problem is NP-complete when:
# it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryi ...
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 mathematical field of graph theory, a bipartite graph (or bigraph) is a graph whose vertices can be divided into two disjoint and independent sets U and V, that is every edge connects a vertex in U to one in V. Vertex sets U and V are ...
.
demonstrated that every proper vertex coloring of a
chordal graph
In the mathematical area of graph theory, a chordal graph is one in which all cycles of four or more vertices have a ''chord'', which is an edge that is not part of the cycle but connects two vertices of the cycle. Equivalently, every induced cy ...
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
In the mathematical field of graph theory, a star coloring of a graph is a (proper) vertex coloring in which every path on four vertices uses at least three distinct colors. Equivalently, in a star coloring, the induced subgraphs formed by the v ...
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