Acyclic 5-choosability of planar graphs without 4-cycles (Q5901353): Difference between revisions

A proper vertex coloring of a graph \(G=(V,E)\) is called acyclic if \(G\) contains no bi-colored cycles. A graph \(G\) is acyclically \(L\)-list colorable if, for a given list assignment \(L=\{L(v) \mid v \in V\}\), there exists a proper acyclic coloring \(\pi\) of \(G\) such that \(\pi(v) \in L(v)\) for all \(v \in V\). If \(G\) is acyclically \(L\)-list colorable for any list assignment with \(|L(v)| \geq k\) for all \(v \in V\), then \(G\) is called acyclically \(k\)-choosable. Every planar graph is conjectured to be acyclically 5-choosable in [\textit{O.V. Borodin}, \textit{D.G. Fon-Der Flaass}, \textit{A.V. Kostochka}, \textit{A. Raspaud}, and \textit{E. Sopena}, ``Acyclic list 7-coloring of planar graphs'', J. Graph Theory 40, No. 2, 83--90 (2002; Zbl 1004.05029)]. The following partial result is established in this paper. Every planar graph without 4-cycles and without 3-cycles at distance less than 3 is acyclically 5-choosable.