Acyclic choosability of graphs with bounded degree (Q2119462): Difference between revisions

From the summary: ``An acyclic coloring of a graph \(G\) is a proper vertex coloring of \(G\) such that every cycle uses at least three colors. For a list assignment \(L = \{L(v) | v \in V(G) \}\), if there exists an acyclic coloring \(\rho\) such that \(\rho(v) \in L(v)\) for each \(v \in V(G)\), then \(\rho\) is called an acyclic \(L-\) list coloring of \(G.\) If there exists an acyclic \(L-\) list coloring of \(G\) for any \(L\) with \(|L(v)| \geq k\) for each \(v \in V(G),\) then \(G\) is called acyclically \(k\)-choosable.'' Here, the authors prove that every graph with maximum degree at most 7 is acyclically 13-choosable. They use the notion of a ``good spanning tree'' to improve the proofs of the results that every graph with maximum degree at most 3 (respectively, at most 4) is acyclically 4-choosable (respectively, 5-choosable).