\((4,1)^*\)-choosability of planar graphs (Q2719962)

A list assignment of a graph \(G\) is a mapping \(L\) that assigns a list \(L(v)\) of colors to each vertex \(v\) of \(G\). An \((L,d)^*\)-coloring is a mapping \(\varphi\) that assigns a color \(\varphi(v) \in L(v)\) to each vertex \(v\) such that \(v\) has at most \(d\) neighbors colored with the same color \(\varphi(v)\). The graph \(G\) is called \((m,d)^*\)-choosable if there exists an \((L,d)^*\)-coloring for every list assignment \(L\) satisfying \(|L(v)|=m\) for all vertices \(v\). The authors prove that every planar graph without 4-cycles is \((4,1)^*\)-choosable.