For a list assignment L of a graph G, a dynamic L-coloring of G is a proper vertex L-coloring of G such that for each vertex u of degree at least 2, the set N(u) of neighbors of u is not monochromatic. For positive integers k, s and t, a (k, s, t)-list assignment of a plane graph G is a list assignment L such that (i) \(|L(v)|\ge k\) for each vertex v of G, (ii) \(|L(x)\cap L(y)|\le s\) for each edge xy of G, and (iii) \(|L(v)\cap L(w)|\le t\) if there is a vertex u such that v, u, w are three consecutive vertices on the boundary of a face. We say that a plane graph G is dynamically (k, s, t)-choosable if G is dynamically L-colorable for any (k, s, t)-list assignment L of G. We show that every plane graph is dynamically (4, 2, 2)-choosable. We also show that Škrekovski’s conjecture about the (3,1)-choosability is equivalent to the statement that all plane graphs are dynamically (3,1,1)-choosable.
