Dynamic coloring parameters for graphs with given genus

Abstract A proper vertex coloring of a graph G is r - dynamic if for each v ∈ V ( G ) , at least min { r , d ( v ) } colors appear in N G ( v ) . In this paper we investigate r -dynamic versions of coloring, list coloring, and paintability. We prove that planar and toroidal graphs are 3-dynamically 10-colorable, and this bound is sharp for toroidal graphs. We also give bounds on the minimum number of colors needed for any r in terms of the genus of the graph: for sufficiently large r , every graph with genus g is r -dynamically ( ( r + 1 ) ( g + 5 ) + 3 ) -colorable when g ≤ 2 and r -dynamically ( ( r + 1 ) ( 2 g + 2 ) + 3 ) -colorable when g ≥ 3 . Furthermore, each of these upper bounds for r -dynamic k -colorability also holds for r -dynamic k -choosability and for r -dynamic k -paintability.