On r-dynamic coloring of graphs in subclasses of planar and circulant graphs - Gutiérrez, Juan; Ugarte, Grover (Anais do Encontro de Teoria da Computação (ETC); 2026: Anais do XI Encontro de Teoria da ComputaçãoDO - 10.5753/etc.2026.21209, 2026)
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 χ d r (G). We determine exact values and upper bounds of χ d r  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.