On dynamic coloring for planar graphs and graphs of higher genus

For integers k,r>0k,r>0, a (k,rk,r)-coloring   of a graph GG is a proper coloring on the vertices of GG by kk colors such that every vertex vv of degree d(v)d(v) is adjacent to vertices with at least min{d(v),r}{d(v),r} different colors. The dynamic chromatic number  , denoted by χ2(G)χ2(G), is the smallest integer kk for which a graph GG has a (k,2k,2)-coloring. A list assignment LL of GG is a function that assigns to every vertex vv of GG a set L(v)L(v) of positive integers. For a given list assignment LL of GG, an (L,rL,r)-coloring of GG is a proper coloring cc of the vertices such that every vertex vv of degree d(v)d(v) is adjacent to vertices with at least min{d(v),r}{d(v),r} different colors and c(v)∈L(v)c(v)∈L(v). The dynamic choice number   of GG, ch2(G)ch2(G), is the least integer kk such that every list assignment LL with |L(v)|=k|L(v)|=k, ∀∀v∈V(G)v∈V(G), permits an (L,2)(L,2)-coloring. It is known that for any graph GG, χr(G)≤chr(G)χr(G)≤chr(G). Using Euler distributions in this paper, we prove the following results, where (2) and (3) are best possible. (1)If GG is planar, then ch2(G)≤6ch2(G)≤6. Moreover, ch2(G)≤5ch2(G)≤5 when Δ(G)≤4Δ(G)≤4.(2)If GG is planar, then χ2(G)≤5χ2(G)≤5.(3)If GG is a graph with genus g(G)≥1g(G)≥1, then ch2(G)≤12(7+1+48g(G)).