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 \square H\). In this paper, we prove that if \(G\) and \(H\) are two graphs and \(\delta(G) \geq 2\), then \(\chi_2(G \square H) \leq \max(\chi_2(G), \chi(H))\). We show that for every two natural numbers \(m\) and \(n\), \(m, n \geq 2\), \(\chi_2(P_m \square P_n) = 4\). Additionally, among other results, it is shown that if \(3\mid mn\), then \(\chi_2(C_m \square C_n) = 3\), and otherwise \(\chi_2(C_m \square C_n) = 4\).