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.

The acyclic chromatic number of the McGee graph is 3.

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. (Grünbaum 1973)
• A(G) ≤ 5 if Δ(G) = 4. (Burstein 1979)
• A(G) ≤ 7 if Δ(G) = 5. (Kostochka & Stocker 2011)
• A(G) ≤ 12 if Δ(G) = 6. (Varagani et al. 2009)

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 and two induced forests. (Stein 1970, 1971)

Algorithms and complexity

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.

Gebremedhin et al. (2008) 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 Skulrattanakulchai (2004).

See also

• Star coloring

References

• Borodin, O. V. (1979), "On acyclic colorings of planar graphs", Discrete Mathematics, 25 (3): 211–236, doi:10.1016/0012-365X(79)90077-3.
• Burstein, M. I. (1979), "Every 4-valent graph has an acyclic 5-coloring (in Russian)", Soobšč. Akad. Nauk Gruzin. SSR, 93: 21–24.
• Grünbaum, B. (1973), "Acyclic colorings of planar graphs", Israel Journal of Mathematics, 14 (4): 390–408, doi:10.1007/BF02764716, S2CID 122808877
• Coleman, Thomas F.; Cai, Jin-Yi (1986), "The Cyclic Coloring Problem and Estimation of Sparse Hessian Matrices" (PDF), SIAM Journal on Algebraic and Discrete Methods, 7 (2): 221–235, doi:10.1137/0607026, hdl:1813/6485.
• Fertin, Guillaume; Raspaud, André (2008), "Acyclic coloring of graphs of maximum degree five: Nine colors are enough", Information Processing Letters, 105 (2): 65–72, CiteSeerX 10.1.1.78.5369, doi:10.1016/j.ipl.2007.08.022, S2CID 12886305.
• Gebremedhin, Assefaw H.; Tarafdar, Arijit; Pothen, Alex; Walther, Andrea (2008), "Efficient Computation of Sparse Hessians Using Coloring and Automatic Differentiation", INFORMS Journal on Computing, 21 (2): 209–223, doi:10.1287/ijoc.1080.0286.
• Jensen, Tommy R.; Toft, Bjarne (1995), Graph Coloring Problems, New York: Wiley-Interscience, ISBN 978-0-471-02865-9.
• Kostochka, A. V. (1978), Upper bounds of chromatic functions of graphs, Doctoral thesis (in Russian), Novosibirsk{{citation}}: CS1 maint: location missing publisher (link).
• Kostochka, Alexandr V.; Stocker, Christopher (2011), "Graphs with maximum degree 5 are acyclically 7-colorable", Ars Mathematica Contemporanea, 4 (1): 153–164, doi:10.26493/1855-3974.198.541, MR 2785823.
• Skulrattanakulchai, San (2004), "Acyclic colorings of subcubic graphs", Information Processing Letters, 92 (4): 161–167, doi:10.1016/j.ipl.2004.08.002.
• Stein, S. K. (1970), "B-sets and coloring problems", Bulletin of the American Mathematical Society, 76 (4): 805–806, doi:10.1090/S0002-9904-1970-12559-9.
• Stein, S. K. (1971), "B-sets and planar maps", Pacific Journal of Mathematics, 37 (1): 217–224, doi:10.2140/pjm.1971.37.217.
• Varagani, Satish; Venkaiah, V. Ch.; Yadav, Kishore; Kothapalli, Kishore (2009), "Acyclic vertex coloring of graphs of maximum degree six", LAGOS'09 – Fifth Latin-American Algorithms, Graphs and Optimization Symposium, Electronic Notes in Discrete Mathematics, vol. 35, Elsevier, pp. 177–182, doi:10.1016/j.endm.2009.11.030, MR 2579427

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.