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). Yadav & Satish (2008) 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.
Read more about this topic: Acyclic Coloring
Famous quotes containing the word complexity:
“In times like ours, where the growing complexity of life leaves us barely the time to read the newspapers, where the map of Europe has endured profound rearrangements and is perhaps on the brink of enduring yet others, where so many threatening and new problems appear everywhere, you will admit it may be demanded of a writer that he be more than a fine wit who makes us forget in idle and byzantine discussions on the merits of pure form ...”
—Marcel Proust (1871–1922)