On r-dynamic coloring of graphs in subclasses of planar and circulant graphs

Abstract

An r-dynamic coloring of a graph G is a proper vertex coloring in which each vertex sees at least min{r, d(v)} distinct colors in its neighborhood. The minimum number of colors in such a coloring is the r-dynamic chromatic number χdr(G). We determine exact values and upper bounds of χdr for several graph classes, including triangular grids, planar 3-trees for r ≤ 4, and planar Eulerian triangulations for r ≤ 3 (with a partial result for r = 4), confirming the conjecture of [Song et al. 2014] for these subclasses. We also establish exact values for the 2-dynamic chromatic number of a subclass of circulant graphs, confirming a conjecture of [Montgomery 2001] for this regular family.