On the r-dynamic coloring of the direct product of a path with either a path or a cycle

1.   Introduction

In 2001, Bruce Montgomery ^[1] (see also ^[2]) introduced the $r$-dynamic proper $k$-coloring of a graph $G = (V(G), E(G))$ as a proper $k$-coloring $c:V(G)\rightarrow \{0, \ldots, k-1\}$ such that the number of colors in the neighborhood $N(v)$ of each vertex $v\in V(G)$ satisfies that

Here, $d(v)$ denotes the degree of the vertex $v$ within the graph $G$. The minimum positive integer $k$ for which such a proper $k$-coloring exists is the $r$-dynamic chromatic number $\chi_r(G)$ of the graph $G$. If $r = 1$, then these concepts are equivalent to the classical notions of proper coloring and chromatic number of a graph. In the literature, one can find a wide amount of studies concerning $r$-dynamic proper $k$-colorings of different types of graphs ^{[3,4,5,6,7,8,9,10,11,12,13]} and products of graphs ^{[14,15,16,17,18,19,20]}. In spite of this, to the best knowledge of the authors, no previous work exists in the literature dealing with the $r$-dynamic coloring of the direct product of graphs. In this regard, this paper is established as a starting point to delve into this topic. More specifically, we focus on the $r$-dynamic chromatic number of the direct product of either two paths or a path and a cycle.

The paper is organized as follows. In Section 2, we describe some preliminary concepts and results on Graph Theory that are used throughout the paper. Then, Sections 3 and 4 deal, respectively, with the $r$-dynamic chromatic number of the direct product of two paths, and of a path and a cycle.

2.   Preliminaries

This section deals with some preliminary concepts and results on Graph Theory that are used throughout the paper. For more details about this topic, we refer the reader to the manuscripts ^[21,22].

A graph is any pair $G = (V(G), E(G))$ that is formed by a set $V(G)$ of vertices and a set $E(G)$ of edges so that each edge joins two vertices, which are then said to be adjacent. From now on, let $vw$ the edge formed by two vertices $v, w\in V(G)$. If $v = w$, then the edge constitutes a loop. A graph is called simple if it does not contain loops. Further, the number of vertices of a graph is its order. A graph is called finite if its order is finite. In this paper, we focus on the direct product $G \times H$ of two finite and simple graphs $G = (V(G), E(G))$ and $H = (V(H), E(H))$, which is the graph having as vertex set the Cartesian product $V(G)\times V(H)$, and so that two vertices $(u, v)$ and $(u', v')$ in such a set are adjacent if and only if $uu' \in E(G)$ and $vv' \in E(H)$. Figure 1 illustrates this last concept.

The set of vertices that are adjacent to a vertex $v\in V(G)$ constitutes its neighborhood $N_G(v)$. The cardinality $d_G(v)$ of this set is the degree of the vertex $v$. If there is no risk of confusion, then we use the respective notations $N(v)$ and $d(v)$. Furthermore, we denote, respectively, $\delta(G)$ and $\Delta(G)$ the minimum and maximum vertex degree of the graph $G$. The following result follows straightforwardly from the previous definitions.

Lemma 1. Let $G$ and $H$ be two finite simple graphs. Then,

a) $d_{G\times H}((v, w)) = d_G(v)d_H(w)$, for all $(v, w)\in V(G\times H)$.

b) $\delta(G\times H) = \delta(G)\delta(H)$.

c) $\Delta(G\times H) = \Delta(G)\Delta(H)$.

A path between two distinct vertices $v$ and $w$ of a given graph $G$ is any ordered sequence of adjacent and pairwise distinct vertices $\langle\, v_0 = v, v_1, \ldots, v_{n-2}, v_{n-1} = w\, \rangle$ in $V(G)$, with $n > 2$. If $v = w$, then such a sequence is called a cycle. A graph is called connected if there always exists a path between any pair of vertices. From here on, let $P_n$ and $C_n$ respectively denote the path and the cycle of order $n$.

A proper $k$-coloring of a graph $G$ is any map $c:V(G)\rightarrow \{0, \ldots, k-1\}$ assigning $k$ colors to the set of vertices $V(G)$ so that no two adjacent vertices have identical color. The minimum positive integer $k$ for which such a proper $k$-coloring exists is the chromatic number $\chi(G)$ of the graph $G$. Concerning the chromatic number of a direct product of graphs, the following result holds.

Lemma 2. Let $G$ and $H$ be two finite simple graphs. Then,

Proof. The first assertion follows straightforwardly from the fact that every proper $k$-coloring $c$ of the graph $G$ (respectively, $H$) induces naturally a proper $k$-coloring $\overline{c}$ of the product graph $G\times H$, which is defined so that $\overline{c}((v, w)) = c(v)$ (respectively, $\overline{c}((v, w)) = c(w)$), for all $(v, w)\in V(G\times H)$.

Disproving the so-called Hedetniemi's conjecture ^[23], it has recently proven ^[24] that the upper bound described in Lemma 2 may not be reached. In any case, the following result is also known.

Theorem 3. ^[25] Let $G$ and $H$ be two finite simple graphs such that $\chi(G) = \chi(H) = k$ and each vertex of the graph $H$ is contained in a complete graph of order $k-1$. Then, the upper bound in Lemma 2 is reached.

Particular cases of proper coloring and chromatic number are the so-called $r$-dynamic proper $k$-coloring and the $r$-dynamic chromatic number, which have already been described in the preliminary section (see (1.1)). The following results are known.

Lemma 4. ^[1] Let $G$ be a graph and let $r$ be a positive integer. Then,

Moreover, $\chi_{r}(G) \leq \chi_{\Delta(G)}(G)$.

It is also known the $r$-dynamic chromatic number of certain graphs.

Lemma 5. ^[7] Let $m$, $n$ and $r$ be three positive integers such that $n > 2$ and $r\geq 2$. The following results hold.

a) $\chi_r(P_n) = 3$.

b) $\chi_r(C_n) = \begin{cases} \begin{array}{ll} 5, & \mathit{\text{if}}\; n = 5, \\ 3, & \mathit{\text{if}}\; n = 3k, \mathit{\text{for some}}\; k\geq 1, \\ 4, & \mathit{\text{otherwise}}. \end{array} \end{cases}$

Further, the following result constitutes a generalization of Lemma 2 in case of dealing with connected graphs with at least one edge.

Lemma 6. Let $G$ and $H$ be two finite simple and connected graphs of order greater than one, and let $r$ be a positive integer such that $r\leq \delta(G')$, for some $G'\in\{G, H\}$. Then, $\chi_r(G\times H)\leq \chi_r(G')$.

Proof. Without loss of generality, let us suppose that $G' = G$. Then, from Lemma 1, together with the fact that both graphs are connected of order greater than one, we have that $r\leq d_G(u)\leq d_G(u)\cdot d_H(v) = d_{G\times H}((u, v))$, for all $(u, v)\in V(G\times H)$. Now, similarly to the proof of Lemma 2, if the map $c:V(G)\rightarrow\{0, \ldots, \chi_r(G)-1\}$ is an $r$-dynamic proper $\chi_r(G)$-coloring of the graph $G$, then the map $\overline{c}:V(G\times H)\rightarrow \{0, \ldots, \chi_r(G)-1\}$ is a proper $\chi_r(G)$-coloring of the direct product $G\times H$. Moreover, for each vertex $(u, v)\in V(G\times H)$, we have that

Hence, the map $\overline{c}$ is an $r$-dynamic proper $\chi_r(G)$-coloring of the direct product $G\times H$. As a consequence, $\chi_r(G\times H)\leq \chi_r(G)$.

3.   Dynamic coloring of the direct product of two paths

In this section, we study the $r$-dynamic chromatic number of the direct product of two paths

and

The following lemma is useful to this end. It establishes a lower bound for the $r$-dynamic chromatic number of a direct product of two graphs under certain conditions. In particular, this result is used in Theorem 8 to determine the $r$-dynamic chromatic number of the direct product of two paths, with $r\geq 2$.

Lemma 7. Let $G$ and $H$ be two finite simple and connected graphs of order greater than two, with two edges $uu'\in E(G)$ and $vv'\in E(H)$ such that $d_G(u) = d_H(v) = 1$ and $d_G(u') = d_H(v') = 2$. If $r\geq 2$, then

Proof. Let $r\geq 2$. The following assertions hold from the hypothesis.

● From Lemma 1, we have that $d_{G\times H}((u, v')) = d_{G\times H}((u', v)) = 2$.

● There exists a vertex $(u'', v'')\in V(G\times H)$ such that $((u', v'), (u'', v''))\in E(G\times H)$.

Then, since $r\geq 2$, every $r$-dynamic proper $k$-coloring of the direct product $G\times H$ assigns different colors to the four vertices $(u, v')$, $(u', v)$, $(u'', v')$ and $(u', v'')$, which describe in turn a cycle $C_4$ within $G\times H$. As a consequence, $k\geq 4$ and the result holds.

Theorem 8. Let $m$, $n$ and $r$ be three positive integers such that $m, n > 2$. Then,

Proof. From Lemma 1, we have that $\Delta(P_m\times P_n) = 4$. Since $\chi(P_m) = \chi(P_n) = 2$, then the case $r = 1$ holds because Lemmas 2.2 and 2.4 imply that

Let us study separately the two remaining cases by defining to this end an appropriate $r$-dynamic proper coloring $c : V\left(P_m \times P_n\right) \rightarrow \left\{0, 1, \ldots\right\}$ satisfying Condition (1.1).

● Case $r\in\{2, 3\}$.

From Lemma 7, we have that $4\leq \chi_r(P_m\times P_n)$, for all $r\geq 2$. Thus, Lemma 4 enables us to focus on proving that $\chi_3(P_m\times P_n)\leq 4$. To this end, let $c : V\left(P_m \times P_n\right) \rightarrow \left\{0, 1, 2, 3\right\}$ be defined such that, for each $(u_i, v_j)\in V(P_m\times P_n)$, we have that

Condition (1.1) holds and hence, $\chi_3(P_m \times P_n) = 4$. Figure 2 illustrates the direct product $P_5\times P_7$.

● Case $r\geq 4$.

From Lemma 4, we have that $5\leq \chi_r(P_m\times P_n)$. In order to prove that this lower bound is reached, let $c : V(P_m\times P_n) \rightarrow \{0, 1, 2, 3, 4\}$ be such that, for each $(i, j, k, l)\in\{0, \ldots, \lfloor\frac m2\rfloor\}\times \{0, 1\}\times \{0, \ldots, \lfloor\frac n{10}\rfloor\}\times\{0, 1, 2, 3, 4\}$, the following assertions hold.

- If $2i+j < m$ and $10k+2l < n$, then

- If $0\leq 2i+j-1 < m$ and $10k+2l+1 < n$, then

Condition (1.1) holds and hence, $\chi_r(P_m \times P_n) = 5$. Figure 3 illustrates the case $m = n = 10$.

4.   Dynamic coloring of the direct product of a path and a cycle

In this section, we focus on the study of the $r$-dynamic chromatic number of the direct product of a path

and a cycle

A series of preliminary results are required to this end. In order to simplify the notation, for each given proper coloring $c:V(P_m\times C_n)\rightarrow \{0, 1, \ldots\}$, we denote $c_{i, j}: = c(u_i, v_j)$, for all $0\leq i < m$ and $0\leq j < n$. In addition, all the indices of the vertices $v_j$ associated to the cycle $C_n$ are considered to be modulo $n$.

Let us start with a result that enables us to focus on those direct products $P_m\times C_n$ such that $n$ is either odd or multiple of four.

Lemma 9. Let $m$, $n$ and $r$ be three positive integers such that $m, n > 2$ and $n$ is odd. Then,

Proof. The result follows straightforwardly from the fact that the direct product $P_m\times C_{2n}$ may be partitioned into two disjoint direct products $P_m\times C_n$.

Now, the following lemma establishes a lower bound for the $2$-dynamic chromatic number of the direct product $P_m\times C_n$, when $n$ is not a multiple of three.

Lemma 10. Let $m$ and $n$ be two positive integers such that $m, n > 2$ and $n\neq 3k$, for any positive integer $k$. Then, $\chi_2(P_m\times C_n) > 3$.

Proof. From Lemma 4, once it is observed that $\Delta(P_m\times C_n) = 4$, we have that $\chi_2(P_m\times C_n)\geq 3$. Hence, it is enough to prove that $\chi_2(P_m\times C_n) = 3$ leads to a contradiction. Thus, let us suppose the existence of a $2$-dynamic $3$-proper coloring $c:V(P_m\times C_n)\rightarrow \{0, 1, 2\}$. In particular, since the vertices $(u_0, v_0)$, $(u_1, v_1)$, $(u_2, v_0)$ and $(u_1, v_{n-1})$ describe a cycle $C_4$ within the direct product $P_m\times C_n$ so that $d((u_0, v_0)) = 2$, we have that

Without loss of generality, we can suppose that $c_{0, 0} = 0$, $c_{1, 1} = 1$ and $c_{1, n-1} = 2$. Then, $c_{2, 0} = 0$. Now, since $d((u_0, v_2)) = 2$, we have that, if $c_{0, 2} = 0$, then it should be $c_{1, 3} = 2$ and hence, $c_{2, 2} = 0$. But then, $|c(N((u_1, v_1))| = 1$, which is a contradiction. So, it must be $c_{0, 2} = 2$ and hence, $c_{1, 3} = 0$. Notice that it is already a contradiction if $n = 4$. So, suppose that $n > 4$. In particular, in order to have a proper coloring, it must be $c_{2, 2} = 2$ (see Figure 4).

By following an iterative similar reasoning, we can ensure that $c_{0, j} = c_{2, j}$, for all $j < n$, and that $c_{1, 2j+1} = (j+1)\, \mod 3$, for all $j < n$ (recall that all the indices of the vertices $v_j$ associated to the cycle $C_n$ are taken modulo $n$). This is a contradiction with the fact that $n\neq 3k$, for any positive integer $k$. Hence, $\chi_2(P_m\times C_n) > 3$.

The following two results deal with $3$-dynamic proper $k$-colorings of the direct product $P_m\times C_n$, with $k\leq 4$.

Lemma 11. Let $m$, $n$ and $k$ be three positive integers such that $m, n > 2$ and $k\leq 4$, and let $c$ be a $3$-dynamic proper $k$-coloring of the direct product $P_m\times C_n$. Then, for each pair of integers $i\in\{1, m-2\}$ and $0\leq j < n$, it must be $\{c_{i, j-3}, c_{i, j+3}\}\subseteq\{c_{i-1, j}, c_{i+1, j}\}$.

Proof. Let us focus on the vertex $c_{i, j-3}$ (the vertex $c_{i, j+3}$ follows a similar reasoning). From Condition (1.1), it must be $|c(N((u_0, v_{j-2})))| = |c(N((u_{m-1}, v_{j-2})))| = 2$. As a consequence, $c_{i, j-3}\neq c_{i, j-1}$, for any $i\in\{1, m-2\}$. Thus, if $c_{i, j-3}\not\in \{c_{i-1, j}, c_{i+1, j}\}$, then the vertex $(u_i, v_{j-1})$ does not verify the mentioned Condition (1.1), because the four adjacent vertices of the vertex $(u_i, v_{j-1})$ could only be colored with at most two colors (see Figure 5).

Proposition 12. Let $m$, $n$ and $k$ be three positive integers such that $m, n > 2$ and $k\leq 4$, and let $c$ be a $3$-dynamic proper $k$-coloring of the direct product $P_m\times C_n$. Then, the following assertions hold for every pair of integers $i\in\{1, m-2\}$ and $0\leq j < n$.

a) $c_{i, j}\neq c_{i, j+4}$.

b) If $c_{i-1, j} = c_{i+1, j}$, then this color is also assigned to both vertices $(u_i, v_{j-3})$ and $(u_i, v_{j+3})$.

c) $\chi_3(P_m\times C_n) > 4$, for all $n\in\{4, 5, 10\}$.

Proof. Let us prove each assertion separately.

a) From Lemma 11, it is $c_{i, j}\in\{c_{i-1, j+3}, c_{i+1, j+3}\}$. Thus, the condition $c_{i, j} = c_{i, j+4}$ contradicts that the map $c$ is a proper coloring.

b) It follows readily from Lemma 11.

c) The case $n = 4$ follows from (a). Now, in order to prove the case $n = 5$, let $j$ be a non-negative integer such that $j\leq 4$. From (a), Condition (1.1) and the fact that $d((u_0, v_{j+1})) = 2$, we have that $c_{1, j}\not\in\{c_{1, j+2}, c_{1, j+4}\}$. In a similar way, $c_{1, j+1}\not\in\{c_{1, j+3}, c_{1, j}\}$, and hence, a fifth color is required. Finally, the case $n = 10$ follows straightforwardly from the case $n = 5$ and Lemma 9.

We focus now on the characterization of $4$-dynamic proper colorings of the direct product $P_m\times C_n$.

Lemma 13. Let $m$, $m'$ and $n$ be three positive integers such that $m, m', n > 2$ and $m'\leq m$. Then, $\chi_4(P_{m'}\times C_n)\leq \chi_4(P_m\times C_n)$.

Proof. Let $c$ be a $4$-dynamic proper $\chi_4(P_m\times C_n)$-coloring of the direct product $P_m\times C_n$. Then, the result follows straightforwardly from the fact that the map $c':V(P_{m'}\times C_n)\rightarrow \{0, 1, \ldots, \chi_4(P_m\times C_n)-1\}$ that is defined so that $c'_{i, j} = c_{i, j}$, for all non-negative integers $i < m'$ and $j < n$, is a $4$-dynamic proper $\chi_4(P_m\times C_n)$-coloring of the direct product $P_{m'}\times C_n$.

Lemma 14. Let $m$ and $n$ be two positive integers such that $m, n > 2$, and let $c$ be a $4$-dynamic proper $5$-coloring of the direct product $P_m\times C_n$. Then, for each pair of integers $0 < i < m-1$ and $0\leq j < n$, it must be

Proof. Let $i$ and $j$ be two integers such that $0 < i < m-1$ and $0\leq j < n$. If $c_{i, j-3}\not\in \{c_{i-1, j}, c_{i+1, j}\}$, then it must be $c_{i, j-1} = c_{i, j-3}$. But then, the vertex $(u_{i-1}, v_{j-2})$ does not satisfy Condition (1.1). A similar reasoning follows for $c_{i, j+3}$ and the vertex $(u_{i-1}, v_{j+2})$, and hence, $\{c_{i, j-3}, c_{i, j+3}\}\subseteq\{c_{i-1, j}, c_{i+1, j}\}$.

Further, since $|c(N((u_i, v_{j-1})))| = |c(N((u_i, v_{j+1})))| = 4$, it must be

Thus, since $|c(N((u_i, v_{j-3})))| = |c(N((u_i, v_{j+3})))| = 4$, we have that

Proposition 15. Let $m$ and $n$ be two positive integers such that $m, n > 2$, and let $c$ be a $4$-dynamic proper $5$-coloring of the direct product $P_m\times C_n$. Then, the following assertions hold.

a) $c_{i, j}\neq c_{i, j+4}$, for all pair of integers $0 < i < m-1$ and $0\leq j < n$.

b) If $m\geq 5$, then $n = 5k$, for some positive integer $k$.

c) $\chi_4(P_m\times C_n) > 5$, for all $n\in\{3, 4, 6, 7, 8, 14\}$.

Proof. Let us prove each assertion separately.

a) From Lemma 14, we have that $c_{i, j}\in\{c_{i-1, j+3}, c_{i+1, j+3}\}$. Then, the result follows from the fact that the map $c$ is a proper coloring.

b) From Lemma 14, we have that $c_{1, 0}\in\{c_{0, 3}, c_{2, 3}\}$. Without loss of generality, let us suppose that $c_{1, 0} = c_{0, 3}$ (the case $c_{1, 0} = c_{2, 3}$ follows similarly by symmetry). Under such an assumption, it is simply verified that the direct product $P_m\times C_n$ is always colored by the map $c$ in a similar way to what is shown in Figure 6.

Notice in particular the requirement that the set $\{c_{i, j}, c_{i, j+1}, c_{i, j+2}, c_{i, j+3}, c_{i, j+4}\}$ is always formed by five distinct colors, whatever the pair of integers $0 < i < m-1$ and $0\leq j < n$ are. The result follows from this fact, together with the colored pattern that is shown in Figure 6.

c) A study of cases is required.

- The case $n = 3$ holds because, from Lemma 14, it should be $\{c_{0, 0}, c_{2, 0}\}\subseteq \{c_{1, 0}, c_{0, 1}, c_{2, 1}\}$. But this contradicts the fact that $|c(N((u_1, v_2)))| = 4$. The case $n = 6$ follows then from Lemma 9.

- The case $n = 4$ follows simply from (a).

- For the case $n = 7$, it is readily verified that the map $c$ should verify that $\{c_{0, 0}, c_{2, 0}\} = \{c_{1, 0}\}\cup(\{c_{0, 1}, c_{2, 1}\}\cap\{c_{0, 6}, c_{2, 6}\})$. As a consequence, it should be $c_{0, 0} = c_{1, 0} = c_{2, 0}$, which contradicts the fact that $|c(N((u_1, v_1)))| = 4$. The case $n = 14$ follows then from Lemma 9.

- Finally, the case $n = 8$ holds because, from Lemma 14, it should be $c_{1, 0}\in\{c_{0, 3}, c_{2, 3}\}\cap\{c_{0, 5}, c_{2, 5}\}$, but this contradicts the fact that $|c(N((u_1, v_4)))| = 4$.

Lemma 16. Let $m\in\{3, 4\}$ and let $n > 2$ be a positive integer such that $\chi_4(P_m\times C_n) = 5$. The following assertions hold.

a) If $n$ is odd, then $\chi_4(P_m\times C_{n+6}) = 5$.

b) If $n$ is even, then $\chi_4(P_m\times C_{n+12}) = 5$.

Proof. From Lemma 4, we have that $\chi_4(P_m\times C_k)\geq 5$, for all $k > 2$. Thus, in order to prove the result, it is enough to define a convenient $4$-dynamic proper $5$-coloring. Moreover, from Lemma 13, it is enough to prove the case $m = 4$. Let us prove each assertion separately for the mentioned case.

a) Let $c$ be a $4$-dynamic proper $5$-coloring of the direct product $P_4\times C_n$, with $n$ odd. Then, let $c':V(P_4\times C_{n+6})\rightarrow \{0, 1, 2, 3, 4\}$ be defined so that the following assertions hold.

- Let $i$ and $j$ be two non-negative integers such that $i < 4$ and $j < n$. Then,

- The remaining vertices of the direct product $P_4\times C_{n+6}$ are colored as follows.

This map $c'$ is a proper coloring of the direct product $P_4\times C_{n+6}$ satisfying Condition (1.1), for $n > 2$ being odd. Figure 19 illustrates the direct product $P_4\times C_{11}$.

b) The case $2 = n\, \mathrm{mod}\, 4$ follows from the previous case and Lemma 9. Finally, the case $0 = n\, \mathrm{mod}\, 4$ follows similarly, but it is necessary to take into account the partition of the direct product $P_m\times C_{n+12}$ into two graphs of the form $P_m\times C_{(n+12)/2}$.

Let us prove now the main result of this section, where we establish the $r$-dynamic chromatic number of the direct product of a path and a cycle.

Theorem 17. Let $m$, $n$ and $r$ be three positive integers such that $m, n > 2$. Then,

Proof. It is known that $\chi(P_m) = 2$, for any positive integer $m$. Moreover, $\chi(C_n) = 2$, if $n$ is even, and $\chi(C_n) = 3$, otherwise. Then, Lemmas 2.2 and 2.4, together with the fact that $\Delta(P_m\times C_n) = 4$, imply that

Let us study separately the remaining cases by defining to this end appropriate $r$-dynamic proper colorings $c : V\left(P_m \times C_n\right) \rightarrow \left\{0, 1, \ldots\right\}$ satisfying Condition (1.1).

Since $\Delta(P_m\times C_n) = 4$, Lemma 4 implies that

The following study of cases arises.

● Case $r = 2$.

The case $n = 3t$ for some positive integer $t$ follows readily from Lemmas 2.5 and 2.6, together with the corresponding lower bound described in (4.1). Otherwise, if $n\neq 3t$, for any positive integer $t$, then Lemma 10 implies that $\chi_2(P_m\times C_n) > 3$. In particular, from Lemmas 2.5 and 2.6, together with the corresponding lower bound described in (4.1), we have that $\chi_2(P_m\times C_n) = 4$, for $n\not\in\{5, 3t\}$, for any positive integer $t$. Finally, if $n = 5$, then it is enough to consider the map $c : V\left(P_m \times C_5\right) \rightarrow \left\{0, 1, 2, 3\right\}$ such that

It is straightforwardly verified that Condition (1.1) holds and hence, $\chi_2(P_m \times C_5) = 4$. Figure 7 illustrates the direct product $P_4\times C_5$.

● Case $r = 3$.

From (4.1), we have that $\chi_3(P_m\times C_n)\geq 4$. Firstly, we study those cases for which this lower bound is reached. In each case, an illustrative $3$-dynamic $4$-proper coloring $c:V(P_m\times C_n)\rightarrow \{0, 1, 2, 3\}$ satisfying Condition (1.1) is given. Once more time, all the indices of the vertices $v_j$ associated to the cycle $C_n$ are taken modulo $n$ throughout the whole proof.

- Subcase $n = 3t$, for some positive integer $t$. Let the map $c$ be defined so that, for each non-negative integer $k < t$, the following assertions hold.

* $c_{0, 3k+1} = 2$.

* $c_{0, 3k+2} = c_{1, 3k+2} = 3$.

* For each non-negative integer $i < t$ and each $j, l\in \{0, 1, 2\}$, if $3i+j+l < m$ and $3k+l < n$, then $c_{3i+j+l, \, 3k+l} = (l-i)\, \mathrm{mod}\, 4$.

It is readily verified that the map $c$ is a proper coloring satisfying Condition (1.1) and hence, $\chi_3(P_m \times C_{3t}) = 4$. Figure 8 illustrates the direct product $P_7\times C_6$.

- Subcase $n = 6t+w$, for some positive integer $t$ and some $w\in\{1, 2\}$. Let the map $c$ be defined so that the following assertions hold, for all non-negative integers $i < m$ and $j < t$.

* For each positive integer $k\leq w$, we have that $c_{i, n-i-k} = (3+i)\, \mathrm{mod}\, 4$.

* For each $(k, l, s)\in\{0, 1, 2\}\times\{0, 1\}\times\{0, \ldots, t-1\}$, we have that $c_{i, 6s+2k+l-i} = (i+k)\, \mathrm{mod}\, 4$.

The map $c$ is a proper coloring satisfying Condition (1.1) and hence, $\chi_3(P_m \times C_{6t+w}) = 4$. Figures 9 and 10 illustrate, respectively, the direct products $P_6\times C_{13}$ and $P_6\times C_{14}$.

- Subcase $n = 6t+5$, for some positive integer.

Firstly, we focus on the case $m$ odd. Let the map $c$ be defined so that the following assertions hold.

* Let $k\in\{0, 1\}$ and let $i$ be a non-negative integer such that $8i+4k < m$. Then,

* Let $k, l\in\{0, 1\}$ and let $i$ be a non-negative integer such that $8i+4k+2l+1 < m$. Then,

* Let $k\in\{0, 1\}$ and let $i$ be a non-negative integer such that $8i+4k+2 < m$. Then,

* Let $k\in\{0, 1\}$ and let $i, j$ be two non-negative integers such that $2i+k < m$ and $16+6j+3k < n$. Then,

* Let $i, j$ be two positive integers such that $2i+1 < m$ and $17+6j < n$. Then,

* Let $i, j$ be two positive integers such that $2i < m$ and $18+6j < n$. Then,

* Let $i, j$ be two positive integers such that $2i < m$ and $20+6j < n$. Then,

* Let $i, j$ be two positive integers such that $2i+1 < m$ and $21+6j < n$. Then,

The map $c$ is a proper coloring satisfying Condition (1.1) and hence, $\chi_3(P_m \times C_{6t+5}) = 4$, for $m$ odd. Figure 11 illustrates the direct product $P_9\times C_{11}$.

Let us focus now on the case $m$ even. Let the map $c$ be defined so that the following assertions hold.

* Let $i, k$ be two non-negative integers such that $k < 7$ and $8i+k < m$. Then,

* Let $i$ be a non-negative integer such that $8i+7 < m$. Then,

* Let $k\in\{0, 1, 2\}$ and let $i, j$ be two positive integers such that $2i < m$ and $16+6j+k < n$. Then,

* Let $i, j$ be two positive integers such that $2i+1 < m$ and $19+6j < n$. Then,

* Let $i, j$ be two positive integers such that $2i < m$ and $20+6j < n$. Then,

* Let $i, j$ be two positive integers such that $2i+1 < m$ and $21+6j < n$. Then,

The map $c$ is a proper coloring satisfying Condition (1.1) and hence, $\chi_3(P_m \times C_{6t+5}) = 4$, for $m$ even. Figure 12 illustrates the direct product $P_{10}\times C_{11}$.

- Subcase $n = 6t+4$, for some positive integer $t\geq 2$.

If $3t+2$ is odd, then it is of the form $6k+5$, for some positive integer $k$, and hence, the result follows from the previous subcase and Lemma 9. Otherwise, if $3t+2$ is even, then it is of the form $8+6k$, for some non-negative integer $k$. Both maps $c$ defined as the ones described for the case $n = 6k+5$ (depending in any case on whether $m$ is odd or even) constitute proper colorings of the direct product $P_m \times C_{8+6k}$ satisfying Condition (1.1). Then, Lemma 9 implies that $\chi_3(P_m \times C_{6t+4}) = 4$. Figure 13 illustrates the direct product $P_9\times C_{28}$.

Let us study now the case $n\in\{4, 5, 10\}$. From Proposition 12, we have that $\chi_3(P_m\times C_n) > 4$, for all $n\in\{4, 5, 10\}$. Then, it is enough to define for each case an illustrative $3$-dynamic $5$-proper coloring $c : V\left(P_m \times C_5\right) \rightarrow \left\{0, 1, 2, 3, 4\right\}$ satisfying Condition (1.1).

- For $n = 4$, let the map $c$ be defined such that for all $(u_i, v_j)\in P_m\times C_4$ we have that

- For $n = 5$, let the map $c$ be defined as $c_{i, j} = (j+2i)\, \mathrm{mod}\, 5$, for all $i < m$ and $j < n$.

Condition (1.1) holds in both cases and hence, $\chi_3(P_m \times C_n) = 5$, for each $n\in\{4, 5\}$. Figure 14 illustrates the case $m = 4$.

Finally, the case $n = 10$ follows from the case $n = 5$ and Lemma 9.

● Case $r\geq 4$.

Since $\Delta(P_m\times C_n) = 4$, Lemma 4 enables us to focus on the case $r = 4$. From (4.1), we have that $\chi_4(P_m\times C_n)\geq 5$. Firstly, we study those cases for which this lower bound is reached. In each case, an illustrative $4$-dynamic $5$-proper coloring $c:V(P_m\times C_n)\rightarrow \{0, 1, 2, 3, 4\}$ satisfying Condition (1.1) is given. Again, indices associated to $C_n$ are taken modulo $n$.

- Subcase $n = 5t$, for some positive integer $t$. If $n$ is odd, then let the map $c$ be defined so that, for all $k < t$,

Condition (1.1) holds and hence, $\chi_4(P_m \times C_{5t}) = 5$, for $t$ odd. Then, the case $t = 2\, \mathrm{mod}\, 4$ follows straightforwardly from Lemma 9. Finally, the just described map $c$ together with the mentioned Lemma 9 enables us to prove the case $t = 0\, \mathrm{mod}\, 4$. Figures 15 and 16 illustrate, respectively, the direct products $P_6\times C_5$ and $P_6\times C_{20}$.

- Subcase $m\in\{3, 4\}$ and $n\not\in\{3, 4, 6, 7, 8, 14\}$. From Lemma 13, it is enough to prove the case $m = 4$. The following study of cases arises.

* $n = 6t+1$, with $t\geq 2$. This case arises from Lemma 16, once we prove in Figure 17 the existence of a $4$-dynamic proper $5$-coloring of the direct product $P_4\times C_{13}$.

* $n = 6t+3$, with $t\geq 1$. This case also arises from Lemma 16, once we prove in Figure 18 the existence of a $4$-dynamic proper $5$-coloring of the direct product $P_4\times C_9$.

* $n = 6t+5$, with $t\geq 1$. This case arises from Lemma 16 and the already known fact that $\chi_4(P_3 \times C_5) = 5$. Figure 19 illustrates the direct product $P_4\times C_{11}$.

* $2 = n\, \mathrm{mod}\, 4$, with $n\not\in\{6, 14\}$. It follows simply from the previous cases and Lemma 9.

* $n = 12t+k$, with $t\geq 1$ and $k\in\{12, 16, 20\}$. This case also arises from Lemma 16, once we prove the existence in Figures 20–22 of $4$-dynamic proper $5$-colorings of the direct products $P_4\times C_{12}$, $P_4\times C_{16}$ and $P_4\times C_{20}$.

Let us focus now on those direct products $P_m\times C_n$, for which the corresponding $4$-dynamic chromatic number is six.

- Subcase $m\in\{3, 4\}$ and $n\in\{3, 4, 6, 7, 8, 14\}$. Again from Lemma 13, it is enough to prove the case $m = 4$. Proposition 15, together with Figures 23 and 24, enables us to ensure that $\chi_4(P_4\times C_3) = \chi_4(P_4\times C_4) = \chi_4(P_4\times C_7) = 6$. Then, Lemma 9 implies that $\chi_4(P_4\times C_6) = \chi_4(P_4\times C_8) = \chi_4(P_4\times C_{14}) = 6$.

- Subcase $m\geq 5$ and $n\neq 5t$, for every positive integer $t$. From Lemma 9, it is enough to study those direct products $P_m\times C_n$ such that $n$ is odd or multiple of four. Keeping in mind this aspect, we are going to focus on the cases $n\in\{3t, 4t, 6t+1, 6t+5\}$, for some positive integer $t$. In each case, an illustrative $4$-dynamic $6$-proper coloring $c: V\left(P_m \times C_n\right) \rightarrow \left\{0, 1, 2, 3, 4, 5\right\}$ satisfying Condition (1.1) is given.

* $n = 3t$, for some positive integer $t$. Let the map $c$ be defined so that

Condition (1.1) holds and hence, $\chi_4(P_m \times C_{3t}) = 6$. Figure 25 illustrates the direct product $P_5\times C_6$.

* $n = 4t$, for some positive integer $t$. Let the map $c$ be defined so that the following assertions hold.

· Let $i$ and $j$ be two non-negative integers such that $2i+1 < m$ and $2j < n$. Then,

· Let $i$ and $j$ be two non-negative integers such that $2i < m$ and $2j+1 < n$. Then,

Condition (1.1) holds and hence, $\chi_4(P_m \times C_{4t}) = 6$. Figure 26 illustrates the direct product $P_{14}\times C_8$.

* $n = 6t+1$, for some positive integer $t$. Let the map $c$ be defined so that the following assertions hold.

· Let $i$ be a positive integer such that $2i+1 < m$. Then,

· Let $i$ be a positive integer such that $2i < m$. Then,

Condition (1.1) holds and hence, $\chi_4(P_m \times C_{6t+1}) = 6$. Figure 27 illustrates the direct product $P_{14}\times C_{13}$.

* $n = 6t+5$, for some positive integer $t$. Let the map $c$ be defined so that the following assertions hold.

· Let $i$ be a positive integer such that $2i+1 < m$. Then,

· Let $i$ be a positive integer such that $2i < m$. Then,

Condition (1.1) holds and hence, $\chi_4(P_m \times C_{6t+5}) = 6$. Figure 28 illustrates the direct product $P_{14}\times C_{11}$.

5.   Conclusion and further works

This paper has explicitly determined the $r$-dynamic chromatic number of the direct product of any given path $P_m$ with either a path $P_n$ or a cycle $C_n$. In this regard, Theorem 8 and 4.9 are the main results of the manuscript. Particularly, it has been obtained that $2\leq\chi_r(P_m\times P_n)\leq 5$ and $2\leq\chi_r(P_m\times C_n)\leq 6$, for all positive integers $m$, $n$ and $r$ such that $m, n > 2$. The significant number of technical results and studies of cases that have been required throughout the paper in order to prove our two main results enables us to ensure that the problem of $r$-dynamic coloring the direct product of two given graphs is not trivial. As such, this paper may be considered as a starting point to delve into this topic. Of particular interest for the continuation of this paper is the study of the $r$-dynamic coloring of two given cycles. The $r$-dynamic coloring of the direct product of either a path or a cycle with other types of graphs is also established as related further work.

Acknowledgments

The authors want to express their gratitude to the anonymous referees for the comprehensive reading of the paper and their pertinent comments and suggestions, which helped improve the manuscript.

Falcón's work is partially supported by the research project FQM-016 from Junta de Andalucía.

Conflict of interest

The authors declare no conflict of interest.