Efficient algorithms for acyclic colorings of graphs (Q1978502)

An acyclic \(k\)-coloring of a graph \(G\) is a coloring of the vertices of \(G\) with at most \(k\) colors such that each color class induces an acyclic subgraph. The vertex arboricity \(a(G)\) of \(G\) is the minimum number \(k\) for which \(G\) has an acyclic \(k\)-coloring. Although the problem of computing \(a(G)\) is NP-hard, \(\rho(G)=1+\lfloor(\max\delta(G'))/2\rfloor\) is known to be a good upper bound on \(a(G)\), where the maximum is taken over all induced subgraphs \(G'\) of \(G\) and \(\delta(G')\) is the minimum degree of \(G'\). In this paper, we present the first linear-time algorithm for acyclic \(\rho(G)\)-colorings. We also give a sufficient condition under which an NC algorithm exists for acyclic \(\rho(G)\)-colorings. Using this condition, we obtain the first NC algorithm for acyclic \(\rho(G)\)-colorings of graphs without a \(K_{3,3}\) (or \(K_{5})\) minor.