Acyclic improper choosability of subcubic graphs

Abstract A d -improper k -coloring of a graph G is a mapping φ : 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 ) ∣ v ∈ V ( G ) } , there exists an acyclic d -improper coloring φ such that φ( v ) ∈  L ( v ) for each vertex v . If G is acyclically d -improper L -colorable for any list assignment L with | L ( v )| ≥  k for all v  ∈  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.