Acyclic improper choosability of subcubic graphs

A d-improper k-coloring of a graph G is a mapping phi : V(G) -> {1, 2, ..., k} such that for every color i, the subgraph induced by the vertices of color i has maximum degree d. That is, every vertex can be adjacent to at most d vertices with being the same color as itself. Such a d-improper k-coloring is further said to be acyclic if for every pair of distinct colors, say i and j, the induced subgraph by the edges whose endpoints are colored with i and j is a forest. Meanwhile, we say that G is acyclically (k, d)*-colorable. A graph G is called acyclically d-improper L-colorable if for a given list assignment L = {L(v) vertical bar v is an element of V(G)}, there exists an acyclic d-improper coloring phi such that phi (v) is an element of L(v) for each vertex v. If G is acyclically d-improper L-colorable for any list assignment L with vertical bar L(v) vertical bar >= k for all v is an element of V, then we say that G is acyclically d-improper k-choosable, or simply say that G is acyclically (k, d)*-choosable. It is known that every subcubic graph is acyclically (2, 2)*-colorable. But there exists a 3-regular graph that is not necessarily acyclically (2, 2)*-choosable. In this paper, we shall prove that every non-3-regular subcubic graph is acyclically (2, 2)*-choosable. (C) 2019 Elsevier Inc. All rights reserved.