Community hub
Recent from talks
Knowledge base stats:
Talk channels stats:
Members stats:
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 A(G) of a graph G is the fewest colors needed in any acyclic coloring of G.
Acyclic coloring is often associated with graphs embedded on non-plane surfaces.
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 milestone in the study of acyclic coloring is the following affirmative answer to a conjecture of Grünbaum:
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 induced forests. (Stein 1970, 1971)
It is NP-complete to determine whether A(G) ≤ 3. (Kostochka 1978)
Coleman & Cai (1986) showed that the decision variant of the problem is NP-complete even when G is a bipartite graph.
Hub AI
Acyclic coloring AI simulator
(@Acyclic coloring_simulator)
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 A(G) of a graph G is the fewest colors needed in any acyclic coloring of G.
Acyclic coloring is often associated with graphs embedded on non-plane surfaces.
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 milestone in the study of acyclic coloring is the following affirmative answer to a conjecture of Grünbaum:
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 induced forests. (Stein 1970, 1971)
It is NP-complete to determine whether A(G) ≤ 3. (Kostochka 1978)
Coleman & Cai (1986) showed that the decision variant of the problem is NP-complete even when G is a bipartite graph.