On r-dynamic Coloring of Grids

Abstract

An \textit{$r$-dynamic $k$-coloring} of a graph $G$ is a proper $k$-coloring of $G$ such that every vertex in $V(G)$ has neighbors in at least $\min \{d(v),r\}$ different color classes. The \textit{$r$-dynamic chromatic number} of a graph $G$, written ${\chi }_r(G)$, is the least $k$ such that $G$ has such a coloring. Proving a conjecture of Jahanbekam, Kim, O, and West, we show that the $m$-by-$n$ grid has no $3$-dynamic $4$-coloring when $mn\equiv 2\mathrm{mod}4$. This completes the determination of the $r$-dynamic chromatic number of the $m$-by-$n$ grid for all $r,m,n$.

Cited by in corpus (5)

• Dynamic coloring of graphs having no $K_5$ minor
• List 3-dynamic coloring of graphs with small maximum average degree
• A counterexample to Montgomery's conjecture on dynamic colourings of regular graphs
• On $r$-dynamic coloring on lexicographic product of star graphs
• On list 3-dynamic coloring of near-triangulations