On the Dynamic Coloring of Cartesian Product Graphs

Abstract

Let $G$ and $H$ be two graphs. A proper vertex coloring of $G$ is called a dynamic coloring if, for every vertex $v$ with degree at least $2$, the neighbors of $v$ receive at least two different colors. The smallest integer $k$ such that $G$ has a dynamic coloring with $k$ colors is denoted by ${\chi }_2(G)$. We denote the Cartesian product of $G$ and $H$ by $G\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}H$. In this paper, we prove that if $G$ and $H$ are two graphs and $\delta (G)\ge 2$, then ${\chi }_2(G\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}H)\le max({\chi }_2(G),\chi (H))$. We show that for every two natural numbers $m$ and $n$, $m,n\ge 2$, ${\chi }_2(P_m\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}{P}_n)=4$. Additionally, among other results, it is shown that if $3\mid mn$, then ${\chi }_2(C_m\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}{C}_n)=3$, and otherwise ${\chi }_2(C_m\mathrm{<img\; draggable="false"\; role="img"\; class="emoji"\; alt="◻"\; src="https://s.w.org/images/core/emoji/15.0.3/svg/25fb.svg">}{C}_n)=4$.