Acyclic improper choosability of subcubic graphs

摘要

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.