On the r-dynamic coloring of the direct product of a path with either a complete graph or a wheel graph

1.   Introduction

In 2001, Bruce Montgomery ^[1] (see also ^[2]) introduced the concept of $r$-dynamic proper $k$-coloring of a graph $G = (V(G), E(G))$ as any proper $k$-coloring $c:V(G)\rightarrow \{0, \ldots, k-1\}$ of such a graph such that

for all $v\in V(G)$. Here, $N(v)$ and $d(v)$ denote, respectively, the neighborhood and the degree of the vertex $v$. In addition, he introduced the notion of $r$-dynamic chromatic number $\chi_r(G)$ of the graph $G$ as the minimum positive integer $k$ for which an $r$-dynamic proper $k$-coloring of $G$ exists. As such, these concepts constitute a natural generalization of the classical notions of proper coloring and the chromatic number $\chi(G)$ of a graph $G$, which arise when $r = 1$. Montgomery himself proposed the natural question about how much the difference between $\chi_r(G)$ and $\chi(G)$ varies, for every $r > 1$, and also whether such a difference is bounded for all graphs. Concerning this last question, he proved ^[1] the existence of graphs for which this difference is unbounded even for $r = 2$. Further, Montgomery also introduced the study of the $r$-dynamic chromatic number of specific families of graphs, for all $r > 1$. More specifically, he determined explicitly all these values for any complete graph, cycle or tree ^[1] and dealt with the case $r = 2$ for any multipartite graph ^[2].

Since the original manuscript of Montgomery, a wide amount of graph theorists have dealt with the study of upper bounds concerning the $r$-dynamic chromatic number of any graph. In this regard, Montgomery himself ^[1] proved that $\chi_2(G)\leq \Delta(G)+3$, for every graph $G$, where $\Delta(G)$ denotes the maximum vertex degree in $G$. Shortly after, Lai et al. ^[2] proved that $\chi_2(G)\leq \Delta(G)+1$, if $\Delta(G)\geq 4$. In addition, Montgomery ^[1] also conjectured that $\chi_2(G)\leq \chi(G)+2$, for every regular graph $G$. This inequality was proved by Lai et al. ^[3] for graphs that are connected and claw-free. Concerning the conjecture itself, it was proved by Akabari et al. ^[4] in case of dealing with bipartite regular graphs. Furthermore, Alishahi ^[5] proved the existence of a constant $c$ such that $\chi_2(G)\leq \chi(G) + c\cdot\ln(k)+1$, for every $k$-regular graph $G$. This last author ^[6] also proved that $\chi_2(G)\leq \chi(G) + \gamma(G)$, where $\gamma(G)$ denotes the domination number of $G$. For a general positive integer $r$, Jahanbekam et al. ^[7] proved that $\chi_r(G)\leq r\cdot \Delta(G)+1$. For $r\geq 2$, Lai et al. ^[3] had already proved that $\chi_r(G)\leq \Delta(G)+r^2-r+1$, whenever $\Delta(G)\leq r$. Finally, concerning the study of upper bounds of the $r$-dynamic chromatic number of products of graphs, Akbari et al ^[8] proved that $\chi_2(G\Box H)\leq \max\{\chi_2(G), \chi_2(H)\}$, if $\delta(G)\geq 2$, where $G\Box H$ denotes the Cartesian product of two graphs $G$ and $H$, and $\delta(G)$ denotes the minimum vertex degree of the graph $G$.

In the recent literature, it is also remarkable the acquired relevance of determining explicitly the $r$-dynamic chromatic number of specific families of graphs, for every positive integer $r$. It is so that this value has already been studied for grid graphs ^[9,7]; helm graphs ^[10]; prism graphs, three-cyclical ladder graphs, joint graphs and circulant graphs ^[11]; toroidal graphs ^[12]; some cycle-related graphs ^[13]; coronations of paths ^[14]; and subdivision-edge coronas of a path ^[15]. In addition, it has also been studied the $r$-dynamic chromatic number of the Cartesian product and the corona product of distinct types of graphs ^{[16,17,18,19,20,21,22]}. Nevertheless, the $r$-dynamic chromatic number of direct products of graphs has only recently been given attention. More specifically, it has explicitly been determined ^[23] for the direct product of any given path with either a path or a cycle. This paper delves into this topic by determining the $r$-dynamic chromatic number of the direct product of any given path with either a complete graph or a wheel graph.

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 a path with either a complete graph or a wheel graph.

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 ^[24,25].

A graph is any pair $G = (V(G), E(G))$ 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$ be 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. This paper deals with the direct product $G \times H$ of two finite and simple graphs $G = (V(G), E(G))$ and $H = (V(H), E(H))$. Its vertex set is the Cartesian product $V(G)\times V(H)$. Two vertices $(v, v')$ and $(w, w')$ in such a set are adjacent if and only if $vw \in E(G)$ and $v'w' \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 finite graph is called complete if all its vertices are pairwise adjacent. 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 said to be connected if there always exists a path between any pair of vertices. Further, if all the vertices of a cycle are joined to a new vertex, then the resulting graph is called a wheel. Such a new vertex is called the center of the wheel graph. From here on, let $K_n$, $P_n$, $C_n$ and $W_n$ respectively denote the complete graph, the path, the cycle and the wheel graph 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$. 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 introductory section (see (1.1)). The following results are known.

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

Moreover,

Lemma 3. ^[3] Let $n$ and $r$ be two positive integers. Then, the following results hold.

a) If $n > 2$, then $\chi_r(P_n) = \begin{cases}\begin{array}{ll} 2, & \mathit{\text{if}}\; r = 1, \\ 3, & \mathit{\text{otherwise}}. \end{array} \end{cases}$

b) $\chi_r(K_n) = n$.

Lemma 4. ^[18] Let $n > 2$ be a positive integer. Then,

In case of dealing with the $r$-dynamic chromatic number of a direct product of graphs, the following results hold.

Lemma 5. ^[23] Let $G$ and $H$ be two finite simple graphs and let $r$ be a positive integer such that $r\leq \delta(G')$, for some $G'\in\{G, H\}$. Then,

Theorem 6. ^[23] Let $m$, $n$ and $r$ be three positive integers such that $m, n > 2$. Then,

3.   Dynamic coloring of the direct product of a path and a complete graph

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

and a complete graph $K_n$ of set of vertices

where $m$ and $n$ are two positive integers such that $m > 2$. From Lemma 1, we have that

More specifically, for each vertex $(u_i, v_j)\in P_m\times K_n$, it is

Firstly, we focus on the case $n\leq 3$, which follows readily from already known results.

Theorem 7. Let $m$ and $r$ be two positive integers such that $m > 2$. Then, the following assertions hold.

a) $\chi_r(P_m\times K_1) = 1$.

b) $\chi_r(P_m\times K_2) = \begin{cases} \begin{array}{ll} 2, & \mathit{\text{if}}\; r = 1, \\ 3, & \mathit{\text{otherwise}}. \end{array} \end{cases}$

c) $\chi_r(P_m\times K_3) = \begin{cases} \begin{array}{ll} r+1, & \mathit{\text{if}}\; r\leq 3, \\ 6, & \mathit{\text{otherwise}}. \end{array} \end{cases}$

Proof. The first assertion follows simply from the fact that the direct product $P_m\times K_1$ is not connected. Further, the second assertion follows from Lemma 3 once it is observed that the direct product $P_m\times K_2$ is formed by a pair of disjoint paths of order $m$. Finally, the third assertion follows from Theorem 6 once it is observed that the complete graph $K_3$ constitutes a cycle of order three.

Now, let us prove a pair of preliminary lemmas that are useful to deal with the case $n > 3$. In order to simplify the notation, for each given proper coloring $c$ of the direct product $P_m\times K_n$, we denote from now on $c_{i, j}: = c(u_i, v_j)$, for all non-negative integers $i < m$ and $j < n$.

Lemma 8. Let $m$, $n$ and $r$ be three positive integers such that $m > 2$, $n > 3$ and $1 < r\leq n-2$. Then,

Proof. Since $r\leq n-2 < \Delta(P_m\times K_n)$, we have from Lemma 2 that $r+1\leq \chi_r(P_m\times K_n)$. Then, in order to prove the result, let us suppose the existence of an $r$-dynamic proper $(r+1)$-coloring $c$ of the direct product $P_m\times K_n$. Since $|c(N((u_0, v_0)))| = r$, we can suppose, without loss of generality, that $c_{1, j} = j$, for all positive integer $j\leq r$. As a consequence, since $c$ is a proper coloring, it must be $c_{0, 0} = 0$. Moreover, there must exist a positive integer $j_0\leq r$ such that $c_{1, r+1} = j_0$. Now, since $|c(N((u_1, v_{r+1})))| = r > 1$ and $c$ is a proper coloring, we have that $j\in \{c_{0, j}, c_{2, j}\}\subseteq\{0, j\}$, for all $j\in\{1, \ldots, r\}\setminus\{j_0\}$, and $c_{0, j_0} = c_{2, j_0} = c_{0, r+1} = c_{2, r+1} = 0$. But then, again from the fact that $c$ is a proper coloring, it must be $c_{1, j} = j_0$, for all $j\in\{0, r+2, \ldots, n-1\}$. It implies that $|c(N((u_0, v_j)))| = r-1 < r$, for all positive integer $j\leq r$ such that $j\neq j_0$, which contradicts Condition (1.1).

Lemma 9. Let $m$, $n$ and $r$ be three positive integers such that $m > 2$, $n > 3$ and $\left\lfloor\frac{3n}2\right\rfloor\leq r\leq 2n-2$. Then,

Proof. Since $r\leq 2n-2 = \Delta(P_m\times K_n)$, we have from Lemma 2 that $r+1\leq \chi_r(P_m\times K_n)$. Let us suppose the existence of an $r$-dynamic proper $(r+1)$-coloring $c$ of the direct product $P_m\times K_n$. Similarly to the proof of Lemma 8, we can suppose, without loss of generality, that $c_{1, j} = j$, for all non-negative integer $j < n$, and $c_{0, j} = n+j$, for all non-negative integer $j < r-n$. Then, since $|c(N((u_1, v_{n-1})))\setminus\{n, \ldots, r-1\}| = n$ and the map $c$ is a proper coloring, it must be $c_{2, j} = j$, for all non-negative integer $j < r-n$, and $j\in\{c_{0, j}, c_{2, j}\}$, for all $j\in\{r-n, \ldots, n-1\}$. But then, since $n+j$ must be a color in the set $c(N((u_1, v_j)))$, for all non-negative integer $j < r-n$, it should also be $n+j\in\{c_{0, r-n}, \ldots, c_{0, n-1}, c_{2, r-n}, \ldots, c_{2, n-1}\}$, for all non-negative integer $j < r-n$. It is only possible if and only if $r-n+1\leq 2n-r-1$. That is, it should be $r\leq \frac {3n}2 -1$, which contradicts the hypothesis.

The following result establishes the $r$-dynamic chromatic number of the direct product of a path and a complete graph of order $n > 3$.

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

Proof. Let us study separately each case by defining an appropriate $r$-dynamic proper coloring $c$ of the corresponding direct product $P_m\times K_n$ satisfying Condition (1.1).

● Case $r = 1$.

This case follows simply from Lemmas 2 and 5 once we notice that $1\leq \delta(P_m)$ and $2 = \chi(P_m)$.

● Case $1 < r\leq n-2$.

From Lemma 8, we have that $r+2\leq \chi_r(P_m\times K_n)$. Then, let the map $c$ be defined so that

Condition (1.1) holds and hence, $\chi_r(P_m\times K_n) = r+2$. Figure 2 illustrates the direct product $P_3\times K_5$, for $r = 3$.

● Case $n-1\leq r < \left\lfloor\frac {3n}2\right\rfloor$.

From Lemma 2, we have that $r+1\leq\chi_r(P_m\times K_n)$. Then, let the map $c$ be defined recursively as follows.

- For each non-negative integer $j < n$, we have that $c_{0, j} = j$.

- For each positive integer $i < m$ and each non-negative integer $j < n$, we have that

Condition (1.1) holds and hence, $\chi_r(P_m\times K_n) = r+1$. Figures 3–5 illustrate the direct product $P_6\times K_5$, for $r\in\{4, 5, 6\}$.

● Case $\left\lfloor\, \frac {3n}2\, \right\rfloor\leq r\leq 2n-2$.

From Lemma 9, it is $r+2\leq \chi_r(P_m\times K_n)$. Then, let the map $c$ be defined so that, for each pair of non-negative integers $i < m$ and $j < n$, we have that

Condition (1.1) holds and hence, $\chi_r(P_m\times K_n) = r+2$. Figure 6 illustrates the direct product $P_5\times K_7$, for $r = 10$.

● Case $r > 2n-2$.

The result follows from the previous case and Lemma 2, once we notice that $\Delta(P_m\times K_n) = 2n-2$.

4.   Dynamic coloring of the direct product of a path and a wheel graph

Let $m$ and $n$ be two positive integers such that $m > 2$ and $n > 3$. In this section, we study the $r$-dynamic chromatic number of the direct product of a path

and a wheel graph $W_n$ of set of vertices

Here, $v$ denotes the center of the wheel graph. Thus, $W_n$ contains the cycle graph

From Lemma 1, we have that

More specifically, for each vertex $(u_i, v_j)\in P_m\times W_n$, it is

In addition, for each vertex $(u_i, v)\in P_m\times W_n$, it is

Firstly, let us prove a result that enables us to focus on those direct products $P_m\times W_n$ such that either $n = 7$, or $n$ is even, or $n = 4t+1$, for some $t\geq 1$.

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

Proof. The result follows straightforwardly from the fact that the direct product $P_m\times W_{2n+1}$ may be considered as two direct products $P_m\times W_{n+1}$, whose sets of vertices are disjoint except for those vertices corresponding to the common center of their respective wheel graphs.

The following preliminary lemmas establish certain bounds for the $r$-dynamic chromatic number $\chi_r(P_m\times W_n)$. In order to simplify the notation, for each given proper coloring $c$ of the direct product $P_m\times W_n$, we denote from now on $c_{i, j}: = c(u_i, v_j)$, for all non-negative integers $i < m$ and $j < n-1$. In addition, all the indices of the vertices $v_j$ associated to the wheel graph $W_n$ are considered to be taken modulo $n-1$. Let us start with a pair of bounds of the $r$-dynamic chromatic number $\chi_r(P_m\times W_n)$ arising from the fact that every wheel graph contains a cycle.

Lemma 12. Let $m$, $n$ and $r$ be three positive integers such that $m > 2$, $n > 3$ and $r > 1$. Then,

whenever there exists an $(r-1)$-dynamic proper $\chi_{r-1}(P_m\times C_{n-1})$-coloring $c$ of the direct product $P_m\times C_{n-1}$ such that the following two conditions hold.

a) $\min\{r, n-1\}\leq \left|\left\{c_{i, j}\colon\, 0\leq j < n-1\right\}\right|$, for all $i\in\{1, m-2\}$.

b) $\min\{r, 2(n-1)\}\leq |\{c_{i-1, j}, \, c_{i+1, j}\colon\, 0\leq j < n-1\}|$, for all positive integer $i\leq m-2$.

Proof. Let us suppose the existence of the map $c$ in the hypothesis. Then, let $\overline{c}:V(P_m\times W_n)\rightarrow \left\{0, \ldots, \chi_{r-1}(P_m\times C_{n-1})\right\}$ be defined so that, for each non-negative integer $i < m$, we have that $\overline{c}((u_i, v)) = \chi_{r-1}(P_m\times C_{n-1})$, and $\overline{c}_{i, j} = c_{i, j}$, for all non-negative integer $j < n-1$. It is simply verified that this map $\overline{c}$ is a proper coloring of the direct product $P_m\times W_n$ satisfying Condition (1.1), for every vertex $(u_i, v_j)\in V(P_m\times W_n)$. Moreover, the compliance of both conditions (a) and (b) enable us to ensure that Condition (1.1) also holds for every vertex $(u_i, v)\in V(P_m\times W_n)$, and hence, the result holds. Figure 7 illustrates this constructive proof for the direct products $P_4\times C_5$ and $P_4\times W_6$.

Let us establish now a series of lower bounds of $\chi_r(P_m\times W_n)$, for $r\geq 2$.

Lemma 13. Let $m > 2$ and $n > 3$ be two positive integers such that $n$ is even. Then,

Proof. From Lemma 2, we have that $3\leq\chi_r(P_m\times W_n)$. Let us suppose the existence of a $2$-dynamic proper $3$-coloring $c$ of the direct product $P_m\times W_n$. Since $n$ is even, there must exist a non-negative integer $j < n-1$ such that $c_{1, j}\neq c_{1, j+2}$ (otherwise, $|c(N(u_0, v))| = 1$, which contradicts Condition (1.1)). Then, without loss of generality, we can take $c_{1, 0} = 0$, $c_{1, 2} = 1$ and $c((u_0, v)) = 2$. As a consequence, $c_{0, 1} = c((u_2, v)) = 2\neq c((u_1, v))$. Again, without loss of generality, we can suppose that $c((u_1, v)) = 0$. Under such assumptions, if there exists a non-negative integer $j_0 < n-1$ such that $c_{0, j_0} = 1$, then it should be $c_{1, j_0-1} = c_{1, j_0+1} = 0$. But then, $|c(N((u_0, v_{j_0})))| = 1$, which is a contradiction. Hence, $c_{0, j} = 2$, for all non-negative integer $j < n-1$. In a similar way, we may ensure that $c_{2, j} = 2$, for all non-negative integer $j < n-1$. But then, $|c(N((u_1, v_j)))| = 1$, for all non-negative integer $j < n-1$, which constitutes again a contradiction. As a consequence, no such a map $c$ exists and hence, the result holds.

Lemma 14. Let $m > 2$ and $n > 3$ be two positive integers such that $n\neq 3k+1$, for all $k > 0$. Then,

Proof. From Lemma 2, we have that $4\leq\chi_r(P_m\times W_n)$. Let us suppose the existence of a $3$-dynamic proper $4$-coloring $c$ of the direct product $P_m\times W_n$. Condition (1.1), together with the fact that $c$ is a proper coloring, implies that $c_{i, j}\neq c((u_1, v))$, for all non-negative integers $i < 3$ and $j < n-1$. As a consequence, for each non-negative integer $j < n-1$, we have that $c_{1, j}\neq c_{0, j+1} = c_{2, j+1}\neq c_{1, j+2}\neq c_{1, j}$. Thus, since $|c(N((u_1, v_{j+2})))| = 3$, it must be $c_{0, j+3} = c_{2, j+3} = c_{1, j}$ and $c_{1, j+4} = c_{0, j+1}$. In short, $c_{1, j}$, $c_{1, j+2}$ and $c_{1, j+4}$ are pairwise distinct, for all non-negative integer $j < n-1$. This contradicts the fact of being $n\neq 3k+1$, for all $k > 0$, and hence, the result holds.

Lemma 15. Let $m > 2$ be a positive integer and let $n\in\{5, 6, 11\}$. Then,

Proof. From Lemma 2, we have that $5\leq\chi_4(P_m\times W_n)$. So, let us suppose the existence of a $4$-dynamic proper $5$-coloring $c$ of the direct product $P_m\times W_n$. Since $d((u_0, v_j)) = 3$, for all non-negative integer $j < n-1$, it must be $c((u_1, v))\not\in\{c_{1, j}\colon\, 0\leq j < n-1\}$. As a consequence, since $|c(N((u_0, v)))| = 4$, we have that $c((u_0, v)) = c((u_1, v)) = c((u_2, v))$. The following study of cases arise.

● Case $n = 5$.

In a recursive way, it is simply verified that $\left|\{c_{i, j}\colon\, 0\leq j < 4\}\right| = 4$ and $c((u_i, v)) = c((u_0, v))$, for all non-negative integer $i < m$. Thus, the map $\overline{c}:V(P_m\times C_4)\rightarrow\{0, 1, 2, 3, 4\}\setminus\{c((u_0, v))\}$ that is defined so that $\overline{c}_{i, j} = c_{i, j}$, for all non-negative integers $i < m$ and $j < 4$ is a $4$-dynamic proper $4$-coloring of the direct product $P_m\times C_4$. It contradicts Theorem 6 and hence, the result holds.

● Case $n = 6$.

Since $|c(N((u_0, v)))| = 4$, we have that $\{c_{1, j}\colon\, 0\leq j\leq 4\} = \{0, 1, 2, 3\}$. Thus, there must exist a pair of non-negative integers $j_1, j_2\leq 4$ such that $c_{1, j_1} = c_{1, j_2}$. Since $|c(N((u_0, v_j)))| = 3$, for all non-negative integer $j < 5$, it must be $(j_2-j_1)\, \mathrm{mod}\, 5\in\{1, 4\}$. Without loss of generality, let us suppose that that $c_{1, 0} = c_{1, 4}$. Then, since $c$ is a proper coloring and $c_{i, j}\neq c((u_1, v))$, for all $(i, j)\in\{0, 2\}\times\{0, 1, 2, 3, 4\}$, we have that $\{c_{0, 1}, c_{2, 1}, c_{0, 3}, c_{2, 3}\}\subseteq\{c_{1, 1}, c_{1, 3}\}$. It contradicts the fact of being $|c(N((u_0, v)))| = 4$ and hence, the result holds.

● Case $n = 11$.

It follows simply from the case $n = 6$ and Lemma 11.

Lemma 16. Let $m > 2$ and $n > 4$ be two positive integers such that one of the following assertions hold.

a) $5\leq n\neq 5t+1$, for all $t\geq 1$.

b) $m\in\{3, 4\}$ and $n\in\{5, 7, 8, 9, 15\}$.

Then,

Proof. Lemma 2 implies that $6\leq\chi_5(P_m\times W_n)$. So, let us suppose the existence of a $5$-dynamic proper $6$-coloring $c$ of the direct product $P_m\times W_n$.

If $n = 5$, then Condition (1.1) implies that $|c(N((u_0, v)))| = 4$ and $|c(N((u_1, v_0)))| = 5$. The first equality enables us to ensure that $c_{1, j}\neq c_{1, k}$, for all non-negative integers $j, k < 4$. But then, the second equality implies that $c_{1, 2}\in N((u_1, v_0))$, which is not possible because $N((u_1, v_0)) = N((u_1, v_2))$ and $c$ is a proper coloring. As a consequence, it must be $6 < \chi_5(P_m\times W_5)$.

In $n > 5$, then Condition (1.1) implies that $|c(N((u_0, v)))| = 5$ and hence, since $c$ is a proper coloring, we have that $c(u_2, v) = c(u_0, v)$. Let $j_0 < n-1$ be a non-negative integer. Since $|c(N((u_1, v_{j_0})))| = 5$, we have that $c(N(u_1, v_{j_0})) = \{0, 1, 2, 3, 4, 5\}\setminus\{c_{1, j_0}, c(u_0, v)\}$. Thus,

As a consequence, $c(u_1, v) = c(u_0, v)$. Moreover, if $m > 3$, then $c_{2, j_0-1}\neq c_{2, j_0+1}$. Thus, if $m\in\{3, 4\}$ (respectively $m\geq 5$) the map $\overline{c}:V(P_3\times C_{n-1})\rightarrow\{0, 1, 2, 3, 4\}\setminus\{c((u_0, v))\}$ that is defined so that $\overline{c}_{i, j} = c_{i, j}$, for all non-negative integers $i < 4$ and $j < n-1$, would be a $4$-dynamic proper $5$-coloring of the direct product $P_3\times C_n$ (respectively, $P_4\times C_n$). It contradicts Theorem 6 when $n\in\{5, 7, 8, 9, 15\}$ (respectively, $n\neq 5t+1$, for all $t\geq 1$) and hence, the result holds.

Lemma 17. Let $m > 2$, $n\geq 4$ and $r\geq 6$ be three positive integers such that $r\leq 2(n-1)$. Then,

Proof. Lemma 2 implies that $r+1\leq\chi_r(P_m\times W_n)$. So, let us suppose the existence of an $r$-dynamic proper $(r+1)$-coloring $c$ of the direct product $P_m\times W_n$. Notice that $c(u_0, v)\neq c(u_2, v)$. Otherwise, we would have, for instance, that $|c(N(u_1, v_0))| < r$, which contradicts Condition (1.1). Now, if $c(u_1, v)\neq c(u_0, v)$, then Condition (1.1) implies that $c(u_0, v)\in c(N(u_1, v))$. But then, $|c(N(u_1, v_j))| < r$, for some non-negative integer $j < n-1$, which contradicts the mentioned condition. Hence, $c(u_1, v) = c(u_0, v)$. Then, again from Condition (1.1) we would have that $c(u_2, v)\in c(N(u_1, v))$ and hence, $|c(N(u_1, v_j))| < r$, for some non-negative integer $j < n-1$. It contradicts once more time Condition (1.1). As a consequence, no $r$-dynamic proper $(r+1)$-coloring exists.

Further, in order to establish an upper bound based on Lemma 5, the following proposition determines the $3$-dynamic chromatic number of a wheel graph.

Proposition 18. Let $m$ and $n$ be two positive integers such that $m > 2$ and $n > 3$. Then,

Proof. Since $\delta(W_n) = 3$, for all $n > 3$, Lemma 5 implies that $\chi_3(P_m\times W_n)\leq \chi_3(W_n)$. In addition, from Lemma 2, we have that $4\leq\chi_3(W_n)$. Let us study separately each case by describing to this end an appropriate $3$-dynamic proper coloring $c$ of the wheel graph $W_n$ satisfying Condition (1.1). An illustrative example of each case is shown in Figure 8.

● Case $n = 3k+1$, for some $k > 0$.

Let the map $c$ be defined so that $c(v) = 3$ and $c(v_j) = j\, \mathrm{mod}\, 3$, for all non-negative integer $j < n-1$. Condition (1.1) holds and hence, $\chi_3(W_n) = 4$. Figure 8 illustrates the case $n = 7$.

● Case $n\neq 3k+1$, for all $k > 0$.

From Condition (1.1), we have that $c(v)$, $c(v_j)$, $c(v_{j+1})$ and $c(v_{j+2})$ are pairwise distinct, for all non-negative integer $j < n-1$. As a consequence, since $n\neq 3k+1$, for all $k > 0$, it must be $4 < \chi_3(W_n)$. The following subcases arise.

- Subcase $n = 3k+2$, for some $k > 0$.

Let the map $c$ be defined so that $c(v) = 4$ and

Condition (1.1) holds and hence, $\chi_3(P_m\times W_n) = 5$. Figure 8 illustrates the case $n = 8$.

- Subcase $n = 3k$, for some $k > 2$.

Let the map $c$ be defined so that $c(v) = 4$ and

Condition (1.1) holds and hence, $\chi_3(P_m\times W_n) = 5$. Figure 8 illustrates the case $n = 9$.

- Subcase $n = 6$.

The result holds because, from Condition (1.1), no two vertices in $W_n$ can share the same color in any given $3$-dynamic proper coloring of the wheel graph $W_6$. An illustrative example is shown in Figure 8.

After enumerating all the previous bounds, we are in condition of determining exactly the $r$-dynamic chromatic number of the direct product $P_m\times W_n$. Firstly, let us establish the $r$-dynamic chromatic number of the direct product $P_m\times W_4$, which follows readily from Theorem 10, once we notice that the wheel graph $W_4$ coincides with the complete graph $K_4$.

Theorem 19. Let $m$ and $r$ be two positive integers such that $m > 2$. Then,

The following theorem is the main result of the section. It establishes the $r$-dynamic chromatic number of the direct product of a path and a wheel graph of order $n\neq 4$.

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

Proof. Let us study separately each case by defining to this end an appropriate $r$-dynamic proper coloring $c$ of the direct product $P_m \times W_n$ satisfying Condition (1.1).

● Case $r = 1$.

This case follows simply from Lemmas 2 and 5 once we notice that $1\leq \delta(P_m)$ and $2 = \chi(P_m)$.

● Case $r = 2$.

From Lemma 2, we have that $3\leq\chi_2(P_m\times W_n)$. Moreover, if $n$ is even, then Lemma 13 implies that $4\leq \chi_2(P_m\times W_n)$. The result holds because, since $r = 2 < 3 = \delta(W_n)$, we have from Lemmas 4 and 5 that

● Case $r = 3$.

From Lemma 2, we have that $4\leq\chi_3(P_m\times W_n)$. Hence, from Proposition 18, we have that $\chi_3(P_m\times W_{3k+1}) = 4$, for all positive integer $k$. Further, Lemma 14 implies that $5\leq \chi_3(P_m\times W_n)$, whenever $n\neq 3k+1$, for all $k > 0$. Hence, again from Proposition 18, we have that $\chi_3(P_m\times W_n) = 5$, for all positive integer $n$ distinct from $6$ and $3k+1$, for all $k > 0$.

Finally, since the $2$-dynamic proper $4$-coloring of the direct product $P_m\times C_5$ that is described in the proof of Theorem 17 in ^[23] satisfies both conditions (a) and (b) of Lemma 12, this last result enables us to ensure that $\chi_3(P_m\times W_6)\leq 5$ and hence, that this upper bound is reached.

● Case $r = 4$.

From Lemma 2, we have that $5\leq\chi_4(P_m\times W_n)$. Then, the following study of cases arise.

- Subcase $n\neq 3k+1$, for all $k > 0$, except for $n\in\{5, 6, 11\}$.

Again from the constructive proof of Theorem 17 in ^[23] and Lemma 12, we can ensure that $\chi_4(P_m\times W_n)\leq 5$. From Lemma 2, this upper bound is reached.

- Subcase $n = 6k+1$, for some $k > 0$.

Let the map $c$ be defined so that $c((u_i, v)) = 4$, for all non-negative integer $i < m$, and such that the following assertions hold.

* $c_{i, j} = c_{i, j\, \mathrm{mod}\, 6}$, for all non-negative integers $i < m$ and $j < n$.

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

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

* $c_{0, 1} = c_{0, 4} = c_{1, 4} = c_{3, 5} = c_{4, 5} = 2$.

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

* Let $j < 6$, $l < 6$ and $t < \lfloor \frac m6\rfloor$ be three non-negative integers such that $6t+j+l < m$. Then,

Condition (1.1) holds and hence, $\chi_4(P_m\times W_n) = 5$. Figure 9 illustrates the direct product $P_7\times W_7$.

- Subcase $n = 6k+4$, for some $k > 0$.

Let the map $c$ be defined so that, for each non-negative integer $i < m$, we have that $c((u_i, v)) = 4$, and

Condition (1.1) holds, and hence, $\chi_4(P_m\times W_n) = 5$. Figure 10 illustrates the direct product $P_{17}\times W_{16}$.

- Subcase $n\in\{5, 6, 11\}$.

From Lemma 15, we have that $6\leq \chi_4(P_m\times W_n)$. In order to prove the case $n = 5$, let the map $c$ be defined so that the following assertions hold.

* $c_{i, j} = j$, for all non-negative integers $i < m$ and $j < n-1$.

* For each non-negative integer $i < m$, we have that

Condition (1.1) holds, and hence, $\chi_4(P_m\times W_5) = 6$. Figure 11 illustrates the direct product $P_4\times W_5$.

Further, both cases $n = 6$ and $n = 11$ follow from Lemma 12 and the respective $4$-dynamic proper $5$-colorings that are described in the proof of Theorem 17 in ^[23].

● Case $r = 5$.

From Lemma 2, we have that $6\leq\chi_5(P_m\times W_n)$. Then, Lemmas 11 and 16 enable us to focus on the following study of cases.

- Subcase $n = 5t+1$, for some $t\geq 1$, or $m\in\{3, 4\}$ and $n\not\in\{5, 7, 8, 9, 15\}$.

Lemma 12, together with the $4$-dynamic proper $5$-colorings that are described in the proof of Theorem 17 in ^[23], enables us to ensure that $\chi_5(P_m\times W_n) = 6$.

- Subcase $n = 5$.

From Lemma 16, we have that $7\leq\chi_5(P_m\times W_5)$. Then, let the map $c$ be defined so that

Condition (1.1) holds, and hence, $\chi_5(P_m\times W_5) = 7$. Figure 12 illustrates the direct product $P_6\times W_5$.

- Subcase $n = 4t+1$, for some $t\geq 2$.

From Lemma 16, we have that $7\leq\chi_5(P_m\times W_n)$. Let the map $c$ be defined so that

In addition, for each $(u_i, v_j)\in V(P_m\times W_n)$, we have that

Condition (1.1) holds, and hence, $\chi_5(P_m\times W_n) = 7$. Figures 13 illustrates the direct product $P_6\times W_{13}$.

- Subcase $n = 7$.

Again from Lemma 16, we have that $7\leq\chi_5(P_m\times W_5)$. Then, let the map $c$ be defined so that $c(u_i, v) = 6$, for all positive integer $i < m$, and

Condition (1.1) holds, and hence, $\chi_5(P_m\times W_7) = 7$. Figure 14 illustrates the direct product $P_6\times W_7$.

- Subcase $n = 6t+k$, for some positive integer $t$ and $k\in\{0, 2, 4\}$.

Let the map $c$ be defined so that

In addition, for each $(u_i, v_j)\in V(P_m\times W_n)$, we have that

Condition (1.1) holds, and hence, $\chi_5(P_m\times W_n)\leq 7$. In particular, Lemmas 11 and 16 imply that $\chi_5(P_m\times W_n) = 7$, for all $m\geq 5$. In addition, they enable us to ensure that $\chi_5(P_m\times W_5) = 7$, for all $n\in\{8, 15\}$ and $m\in\{3, 4\}$. Figures 15–17 illustrate the direct products $P_6\times W_n$, for $n\in\{12, 14, 16\}$.

● Case $r = 6$.

From Lemma 17, we have that $8\leq\chi_r(P_m\times W_n)$. Then, Lemma 11 enables us to focus on the following study of cases. In all of them, the described map $c$ satisfies that

- Subcase $n = 7$.

Let the map $c$ be defined so that

Condition (1.1) holds, and hence, $\chi_6(P_m\times W_7) = 8$. Figure 18 illustrates the case $m = 7$.

- Subcase $n = 4t+1$, with $t\geq 2$.

Let the map $c$ be defined so that

Condition (1.1) holds, and hence, $\chi_6(P_m\times W_n) = 8$. Figure 19 illustrates the case $m = 7$.

- Subcase $n = 6t$, with $t\geq 1$.

Let the map $c$ be defined so that

and, for each pair of non-negative integers $j$ and $k\leq 5$ such that $6j+k+5 < n-1$, we have that

Condition (1.1) holds, and hence, $\chi_6(P_m\times W_n) = 8$. Figure 20 illustrates the direct product $P_7\times W_{12}$.

- Subcase $n = 6t+2$, with $t\geq 1$.

Let the map $c$ be defined so that, for each non-negative integer $j < n-1$, we have that

and

In addition, the following assertions hold.

* Let $k$ be a positive integer such that $2k < m$. Then,

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

Condition (1.1) holds, and hence, $\chi_6(P_m\times W_n) = 8$. Figure 21 illustrates the direct product $P_6\times W_{14}$.

- Subcase $n = 6t+4$, with $t\geq 1$.

Let $c$ be the map defined in the previous subcase ($n = 6t+2$). Then, let the map $c'$ be defined so that, for each pair of non-negative integers $i < m$ and $j < n-1$, we have that

Condition (1.1) holds, and hence, $\chi_6(P_m\times W_n) = 8$. Figure 22 illustrates the direct product $P_6\times W_{16}$.

● Case $7\leq r\leq 2(n-1)$.

From Lemma 17, we have that $r+2\leq\chi_r(P_m\times W_n)$. The following study of cases arises. In all of them, the described map $c$ satisfies that

- Subcase $r\leq n-1$.

Let $t < r$ be such that $n-1\equiv t\, (\mathrm{mod}\, r)$. Then, let the map $c$ be defined so that

Condition (1.1) holds, and hence, $\chi_r(P_m\times W_n) = r+2$. Figure 23 illustrates the direct product $P_5\times W_{12}$, for $r = 8$.

- Subcase $n+2\leq r$.

Let $c$ be the map just described in the previous subcase ($r\leq n-1$). Then, let the map $c'$ be defined so that

Condition (1.1) holds, and hence, $\chi_r(P_m\times W_n) = r+2$. Figure 24 illustrates the direct product $P_6\times W_7$, for $r = 8$.

5.   Conclusion and further works

This paper has delved into the study of the $r$-dynamic chromatic number of the direct product of two given graphs. More specifically, it has explicitly been determined the $r$-dynamic chromatic number of the direct product of any given path $P_m$ with either a complete graph $K_n$ or a wheel $W_n$. In this regard, Theorems 3.4, 4.9 and 4.10 are the main results of the manuscript. Particularly, it has been obtained that $r+1\leq\chi_r(P_m\times G)\leq 2n$, for all $G\in\{K_n, W_n\}$. In addition, we have also established in Proposition 18 the $3$-dynamic chromatic number of any wheel graph.

Similarly to the previous work of the authors in the topic ^[23], a significant number of technical results is required in order to prove the main theorems of the paper. This fact enables us to corroborate that the problem of $r$-dynamic coloring the direct product of two given graphs is not trivial at all. Of particular interest for the continuation of this paper is the study of the $r$-dynamic coloring of the direct product of two complete graphs and that one concerning the direct product of two wheel graphs. The $r$-dynamic coloring of the direct product of a path, a complete graph or a wheel 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. Further, Falcón's work is partially supported by the research project FQM-016 from Junta de Andalucíi a, and the Departmental Research Budget of the Department of Applied Mathematics I of the University of Seville.

Conflict of interest

The authors declare no conflict of interest.