On rr-dynamic coloring of graphs

An rr-dynamic proper  kk-coloring   of a graph GG is a proper kk-coloring of GG such that every vertex in V(G)V(G) has neighbors in at least min{d(v),r}min{d(v),r} different color classes. The rr-dynamic chromatic number   of a graph GG, written χr(G)χr(G), is the least kk such that GG has such a coloring. By a greedy coloring algorithm, χr(G)≤rΔ(G)+1χr(G)≤rΔ(G)+1; we prove that equality holds for Δ(G)>2Δ(G)>2 if and only if GG is rr-regular with diameter 2 and girth 5. We improve the bound to χr(G)≤Δ(G)+2r−2χr(G)≤Δ(G)+2r−2 when δ(G)>2rlnnδ(G)>2rlnn and χr(G)≤Δ(G)+rχr(G)≤Δ(G)+r when δ(G)>r2lnnδ(G)>r2lnn.In terms of the chromatic number, we prove χr(G)≤rχ(G)χr(G)≤rχ(G) when GG is kk-regular with k≥(3+o(1))rlnrk≥(3+o(1))rlnr and show that χr(G)χr(G) may exceed r1.377χ(G)r1.377χ(G) when k=rk=r. We prove χ2(G)≤χ(G)+2χ2(G)≤χ(G)+2 when GG has diameter 2, with equality only for complete bipartite graphs and the 5-cycle. Also, χ2(G)≤3χ(G)χ2(G)≤3χ(G) when GG has diameter 3, which is sharp. However, χ2χ2 is unbounded on bipartite graphs with diameter 4, and χ3χ3 is unbounded on bipartite graphs with diameter 3 or 3-colorable graphs with diameter 2. Finally, we study χrχr on grids and toroidal grids.