Acyclic colorings of graphs with bounded degree (Q310229)

A \(k\)-coloring of a graph \(G\) is a partition of its \(V(G)\) into disjoint color classes \(V_1, V_2,\dots,V_k\). In the traditional use of the term, it was usually required that the vertices in each color class be independent; where that is the case, the coloring is proper; but in this paper colorings may be improper, and that term is used to mean not necessarily proper. A coloring is acyclic if the subgraph induced by the edges whose ends are in \(V_i\cup V_j\) is acyclic (\(i,j=1,2,\dots,k\)). \({\mathcal S}_d\) denotes the class of graphs of maximum degree not exceeding \(d\), and \({\mathcal D}_1\) denotes the class of acyclic graphs. For non-empty classes \({\mathcal P}_1,{\mathcal P}_2,\dots,{\mathcal P}_k\) of graphs, each closed under isomorphism, a \(k\)-coloring of \(G\) is a \(({\mathcal P}_1,{\mathcal P}_2,\dots,{\mathcal P}_k)\)-coloring if the subgraph induced in \(G\) by \(V_i\) belongs to \({\mathcal P}_i\) \((i=1,2,\dots,k)\); where \({\mathcal P}_i={\mathcal P}\) (\(i=1,2,\dots,k\)), the term is reduced to \({\mathcal P}^{(k)}\)-coloring. The authors continue an investigation begun in [\textit{A. Fiedorowicz} and \textit{E. Sidorowicz}, Sci. China, Math. 57, No. 12, 2485--2494 (2014; Zbl 1308.05048)]: Theorem 3.1: Every graph \(G\in{\mathcal S}_5\) has an acyclic \(({\mathcal S}_4\cap{\mathcal D}_1)^{(5)}\)-coloring. Theorem 4.6: The problem of deciding whether a graph admits an acyclic \(({\mathcal S}_3,{\mathcal S}_3)\)-coloring is NP-complete, even for graphs with maximum degree at most 5. An acyclic \(({\mathcal S}_d)^{(k)}\)-coloring is called an acyclic \(d\)-improper \(k\)-coloring. Theorem 5.1: For every fixed \(d\), \(d\geq4\), there exists a linear (in \(n\)) algorithm finding an acyclic \((d-1)\)-improper coloring for any \(n\)-vertex graph \(G\) with maximum degree at most \(d\), using \(\left\lfloor\frac{d^2}4\right\rfloor+1\) colors. Theorem 5.2: Let \(d\) and \(t\) be fixed, such that \(2\leq t\leq\left\lfloor\frac d2\right\rfloor-1\). There exists a linear (in \(n\)) algorithm finding an acyclic \((d-t)\)-improper coloring for any \(n\)-vertex graph \(G\) with maximum degree at most \(d\), using \(\left\lfloor\frac{d^2}4\right\rfloor+t+1\) colors. The authors propose Open Problem 6.1: Let \(G\) be a graph with maximum degree at most 5. For which properties \(\mathcal P\) does \(G\) admit an acyclic \(({\mathcal P})^{(5)}\)-coloring?