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.