2015/11/12 by Sarah Loeb, Loeb, Sarah, Thomas Mahoney +5 · 1 citation
Mathematics · #05C10 #05C15 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05C10 #msc:05C15
paper · pdf · doi:10.48550/arxiv.1511.03983
19 pages, 18 figures
arxiv created 2015/11/12 · arxiv updated 2015/11/13
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 NG(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)(2g+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. We develop a method to prove that certain configurations are reducible for each of the corresponding r-dynamic parameters.