Acyclic Choosability of Graphs with Bounded Degree

An acyclic colouring of a graph G is a proper vertex colouring such that every cycle uses at least three colours. For a list assignment L = {L(v)∼ v ∈ V(G)}, if there exists an acyclic colouring ρ such that ρ(v) ∈ L(v) for each v ∈ V(G), then ρ is called an acyclic L-list colouring of G. If there exists an acyclic L-list colouring of G for any L with ∣L(v)∣> k for each v ∈ V (G), then G is called acyclically k-choosable. In this paper, we prove that every graph with maximum degree Δ ≤ 7 is acyclically 13-choosable. This upper bound is first proposed. We also make a more compact proof of the result that every graph with maximum degree Δ ≤ 3 (resp., Δ ≤ 4) is acyclically 4-choosable (resp., 5-choosable).