<figure><img src="image_1.png" /></figure>

HAL
open science

# On the [r, s, t]-coloring of the square of cylindrical grids

Brice Effantin

► To cite this version:

Brice Effantin. On the [r, s, t]-coloring of the square of cylindrical grids. Discrete Mathematics Letters, 2025, 15, pp.15-22. 10.47443/dml.2024.148 . hal-04892915

HAL Id: hal-04892915

https://hal.science/hal-04892915v1

Submitted on 2 May 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
Research Article

# On the [r, s, t]-coloring of the square of cylindrical grids

Brice Effantin*

Université de Lyon, Université Claude Bernard Lyon 1, CNRS, INSA Lyon, Laboratoire d'InfoRmatique en Image et Systèmes d'information UMR 5205, Ecole Centrale de Lyon, Université Lyon 2, F-69622 Villeurbanne, France

(Received: 26 August 2024. Received in revised form: 5 January 2025. Accepted: 13 January 2025. Published online: 15 January 2025.)

© 2025 the author. This is an open-access article under the CC BY (International 4.0) license (www.creativecommons.org/licenses/by/4.0/).

## Abstract

The [r, s, t]-coloring is a generalization of the classical vertex, edge, and total colorings, where two vertices, two edges, and a vertex and its incident edges have colors distant by at least r, s, and t, respectively. The square of a graph G is a graph obtained from G by adding an edge between two vertices at a distance at most 2 in G. A cylindrical grid is equivalent to the Cartesian product of a path and a cycle. In this article, colorings for the square of cylindrical grids are discussed. It is shown that such graphs are class one graphs (according to Vizing's theorem). For the [r, s, t]-coloring of these graphs, particular values of r, s, and t are presented, for which the minimum number of colors needed in an [r, s, t]-coloring is determined.

**Keywords:** edge coloring; Cartesian product; total coloring; vertex coloring.

**2020 Mathematics Subject Classification:** 05C15.

## 1. Introduction

In graph coloring, a vertex coloring of a graph G is an assignment of colors to the vertices of G such that adjacent vertices are colored differently. Analogously, different colors are assigned to adjacent edges in an edge coloring. In a total coloring of a graph G, colors are given to both vertices and edges of the graph, such that two adjacent vertices, two adjacent edges or a vertex and its incident edges must have different colors. A coloring of a graph G = (V, E) with vertex set V and edge set E is then defined as a function c on S into a set of colors where S represents V, E or V ∪ E for respectively the vertex, edge and total colorings. For every coloring, a parameter is defined as the minimum number of colors used to provide this coloring. The chromatic number χ(G), the chromatic index χ'(G) and the total chromatic number χ''(G) are the parameters related to respectively the vertex, edge and total colorings. In 2007 a new coloring was introduced in [8] that generalizes several of these colorings. Let G = (V, E) be a graph with vertex set V and edge set E. Given nonnegative integers r, s, and t, a [r, s, t]-coloring of a graph G is a function c from V ∪ E to the color set {0, 1, ..., k − 1} such that |c(xᵢ) − c(xⱼ)| ≥ r for every two adjacent vertices xᵢ, xⱼ ∈ V, |c(eᵢ) − c(eⱼ)| ≥ s for every two adjacent edges eᵢ, eⱼ ∈ E, and |c(xᵢ) − c(eⱼ)| ≥ t for every vertex xᵢ and an incident edge eⱼ. Thus a [r, s, t]-coloring is a generalization of the three classical colorings: a [1,0,0]-coloring represents a vertex coloring, a [0,1,0]-coloring is an edge coloring and a [1,1,1]-coloring corresponds to a total coloring. The minimum number k such that G admits a [r, s, t]-coloring is called the [r, s, t]-chromatic number and is denoted by χ_{r,s,t}(G). The [r, s, t]-coloring can have many applications in different fields, like in scheduling [8] (to elaborate a planning with different constraints), for the channel assignment problem (where different labels representing frequencies are assigned to vertices and edges), etc.

In [8], the authors gave some properties of the [r, s, t]-chromatic number and proved several general bounds on the parameter; for instance, see the next result.

**Theorem 1.1.** [8] For a graph G,

$$ \max\{r(\chi(G) - 1) + 1, s(\chi'(G) - 1) + 1, t + 1\} \leq \chi_{r,s,t}(G) \leq r(\chi(G) - 1) + s(\chi'(G) - 1) + t + 1. $$

They also presented exact values and some bounds for the parameter according to particular values of r, s, and t (min{r, s, t} = 0, r = s = 1, r = t = 1, s = t = 1, ...) and investigated the class of complete graphs. In [16] and [17], the [r, s, t]-chromatic number was completely determined for paths and cycles for any value of r, s, and t. The study of stars was done in [7] and these graphs were also studied in [3] and extended to bipartite graphs and trees. Some graph products were also considered in [4].

<footnote>*E-mail address: brice.effantin-dit-toussaint@univ-lyon1.fr</footnote>
In the following, graphs without loops or multiple edges are considered where the maximum degree of a graph G is denoted by $\Delta(G)$. In the graphs, every edge $e = xy$ with end vertices $x$ and $y$ is undirected. The Cartesian product of two graphs G and H, denoted by $G \square H$, is the graph with vertex set $V(G) \times V(H)$ and the neighborhood of a vertex $(x_1, x_2)$ is $N((x_1, x_2)) = (\{x_1\} \times N_H(x_2)) \cup (N_G(x_1) \times \{x_2\})$, where $N_G(x)$ is the neighborhood of $x$ in G. Thus for a path $P_n$ and a cycle $C_m$, the graph $P_n \square C_m$ is isomorphic to a cylindrical grid. Cartesian products of graphs attracted many attention for different problems (coloring, domination, etc.) [1, 6, 9, 10].

The square of a graph G, denoted by $[G]^2$, is defined from G by $V([G]^2) = V(G)$ and any edge $xy \in E([G]^2)$ verifies either $xy \in E(G)$ or $x$ and $y$ have a common neighbor in G. The graph $[G]^2$ will be called a *squared graph*. The problem of coloring squared graphs has been very studied. Several works focused on the chromatic number of squared planar graphs [5, 11, 14, 15]. And Xue et al. [18] considered the chromatic and the equitable chromatic numbers of squared Sierpiński graphs. The chromatic number of the square of Cartesian products was also investigated. Sopena and Wu [13] (completed by Shao and Vesel [12]) were interested in the Cartesian product of two cycles, while Chiang and Yan [2] considered the Cartesian product of paths and cycles. In particular, they proved

**Theorem 1.2.** [2] Let $n \ge 2$ and $G = C_m \square P_n$. Then

$$ \chi([G]^2) = \begin{cases} 2 & \text{if } n = 2 \text{ and } m \equiv 0(\text{mod } 4), \\ 5 & \text{if } n = 2 \text{ and } m \in \{3, 6\}, \\ 5 & \text{if } n \ge 3 \text{ and } m \not\equiv 0(\text{mod } 5), \\ 4 & \text{otherwise.} \end{cases} $$

In this article, we discuss the $[r, s, t]$-coloring of squared cylindrical grids. In particular, we prove that the general bounds of the $[r, s, t]$-chromatic number given in Theorem 1.1 are tight since both are reachable under conditions for $r$, $s$, and $t$. In Theorem 1.1, the bounds are based on the chromatic index of the considered graphs and we also investigate this parameter for squared cylindrical grids. Thus, we start with some notations in Section 2. Then, in Section 3, we characterize the chromatic index of such grids while in Section 4 we discuss $[r, s, t]$-colorings of these graphs.

## 2. Notations

Let G and H be two graphs such that $V(G) = \{x_1, x_2, \dots, x_{n_G}\}$ and $V(H) = \{y_1, y_2, \dots, y_{n_H}\}$. By definition, the graph $G \square H$ can be viewed as a grid where the $n_G$ rows are $n_G$ copies of H (denoted by $H^1, H^2, \dots, H^{n_G}$) and the $n_H$ columns are $n_H$ copies of G (denoted by $G^1, G^2, \dots, G^{n_H}$). A vertex in $G \square H$ is then denoted by $x_{i,j}$ where $i$ is the column and $j$ the row in the grid (i.e. the vertex in $G^i$ and $H^j$).

The squared graph of the Cartesian product $G \square H$ is denoted by $[G \square H]^2$. Edges $E([G \square H]^2)$ can be decomposed into three subsets. On one hand, we said that $G \square H$ has some copies of G and H. The first subset contains the edges from the copies $G^i$ and $H^j$. We denote this set by $\mathcal{E}([G \square H]^2) = \{\bigcup_{i=1}^{n_H} E(G^i), \bigcup_{j=1}^{n_G} E(H^j)\}$. On the other hand, the remaining edges (i.e. edges due to the power 2) can be distributed into two subsets. The edges due to the power two in all the copies $G^i$ and $H^j$ form the set of power edges (denoted by $\mathcal{P}([G \square H]^2)$) while the edges added between copies of $[G^i]^2$ and $[H^j]^2$ form the cross edges (denoted by $\mathcal{C}([G \square H]^2)$). Thus we have $E([G \square H]^2) = \mathcal{E}([G \square H]^2) \cup \mathcal{P}([G \square H]^2) \cup \mathcal{C}([G \square H]^2)$. We can see that sets $\mathcal{E}$ and $\mathcal{P}$ can be used for any graph, while the set $\mathcal{C}$ is specific to the Cartesian products.

Note that for a subset $E' \subseteq E(G)$, the number of colors used to properly color $E'$ will be denoted by $\eta(E')$.

## 3. The chromatic index of a squared cylindrical grid

In this section, we give the chromatic index of a squared cylindrical grid. We start with preliminary results to evaluate the number of colors needed for each set of edges in $[P_n \square C_m]^2$.

We first recall the chromatic index of a path and a cycle, and we deduce the number of colors needed for the power edges of a squared path and a squared cycle.

**Fact 3.1.** Let $P_n$ and $C_m$ be respectively a path of order $n \ge 2$ and a cycle of order $m \ge 3$. Then,

$$ \chi'(P_n) = \begin{cases} 1 & \text{if } n = 2, \\ 2 & \text{otherwise,} \end{cases} $$

$$ \chi'(C_m) = \begin{cases} 2 & \text{if } m \text{ is even,} \\ 3 & \text{otherwise.} \end{cases} $$

**Proposition 3.1.** Let $P_n$ be a path of order $n \ge 3$. Then $\eta(\mathcal{P}([P_n]^2)) = 2$ if $n \ge 5$ and $\eta(\mathcal{P}([P_n]^2)) = 1$ otherwise.

**Proof.** Edges of $\mathcal{P}([P_n]^2)$ form two independent paths of order $n/2$ if $n$ is even (and of orders $\lfloor n/2 \rfloor$ and $\lceil n/2 \rceil$ if $n$ is odd) colorable with the same colors. Thus $\eta(\mathcal{P}([P_n]^2)) = \max\{\chi'(P_{\lfloor n/2 \rfloor}), \chi'(P_{\lceil n/2 \rceil})\}$ and Fact 3.1 gives the result. $\square$
**Proposition 3.2.** Let $C_m$ be a cycle of order $m \ge 4$. Then

$$ \eta(\mathcal{P}([C_m]^2)) = \begin{cases} 1 & \text{if } m = 4, \\ 2 & \text{if } m > 4 \text{ and } m, \frac{m}{2} \text{ are even,} \\ 3 & \text{otherwise.} \end{cases} $$

**Proof.** If $m = 4$, then edges of $\mathcal{P}([C_m]^2)$ form two independent paths $P_2$ colorable with the same unique color. Consider an even $m > 4$. Edges of $\mathcal{P}([C_m]^2)$ form two independent cycles of order $\frac{m}{2}$. Thus, by Fact 3.1, we need 2 colors if $\frac{m}{2}$ is even and 3 colors otherwise. Moreover, if $m$ is odd, the edges of $\mathcal{P}([C_m]^2)$ form a unique cycle of order $m$ which needs 3 colors by Fact 3.1. □

Then we evaluate the number of colors needed to properly color each subset of $E([P_n \square C_m]^2)$ and we start with the following property.

**Property 3.1.** Let $P_n$ and $C_m$ be respectively a path of order $n \ge 2$ and a cycle of order $m \ge 3$. Then

$$ \eta(\mathcal{E}([P_n \square C_m]^2)) \le \begin{cases} \chi'(P_n) + \chi'(C_m) & \text{if } m \text{ is even,} \\ \chi'(P_n) + \chi'(C_m) - 1 & \text{otherwise,} \end{cases} \quad (a) \quad (b) $$

and

$$ \eta(\mathcal{P}([P_n \square C_m]^2)) \le \begin{cases} \eta(\mathcal{P}([C_m]^2)) & \text{if } n = 2, \\ \eta(\mathcal{P}([P_n]^2)) & \text{if } m = 3, \\ \eta(\mathcal{P}([P_n]^2)) + \eta(\mathcal{P}([C_m]^2)) & \text{if } m \text{ and } \frac{m}{2} \text{ are even,} \\ \eta(\mathcal{P}([P_n]^2)) + \eta(\mathcal{P}([C_m]^2)) - 1 & \text{otherwise.} \end{cases} \quad (c) \quad (d) \quad (e) \quad (f) $$

**Proof.** First, note that if $n = 2$ (case (c)), then $\mathcal{P}([P_n]^2) = \emptyset$ and $\eta(\mathcal{P}([P_n \square C_m]^2)) = \eta(\mathcal{P}([C_m]^2))$. By the same way, if $m = 3$ (case (d)), then $\mathcal{P}([C_m]^2) = \emptyset$ and $\eta(\mathcal{P}([P_n \square C_m]^2)) = \eta(\mathcal{P}([P_n]^2))$.

Then, we see in $[P_n \square C_m]^2$ that all the copies of $P_n$ (respectively, $C_m$) are distinct and can be colored with the same coloring. Moreover, copies $P_n^i$ and $C_m^j$ share some vertices and need different colorings, with $1 \le i \le m$ and $1 \le j \le n$. Thus edges of $\mathcal{E}([P_n \square C_m]^2)$ are colorable with at most $\chi'(P_n) + \chi'(C_m)$ colors (case (a)). The same reasoning is done for the copies of $\mathcal{P}([P_n]^2)$ and $\mathcal{P}([C_m]^2)$. Thus, power edges of $[P_n \square C_m]^2$ are colorable with at most $\eta(\mathcal{P}([P_n]^2)) + \eta(\mathcal{P}([C_m]^2))$ colors (case (e)).

Consider $m$ is odd (respectively, $m$ or $\frac{m}{2}$ is odd). Color each copy of $C_m$ (respectively, $\mathcal{P}([C_m]^2)$) with the same 3-coloring. Note that vertices of a copy $P_n^i$ (respectively, $\mathcal{P}([P_n^i]^2)$) have only two colors on incident colored edges from the copies of $C_m$ (respectively, $\mathcal{P}([C_m]^2)$). Then each copy $P_n^i$ (respectively, $\mathcal{P}([P_n^i]^2)$) can be colored with one already used color and $\chi'(P_n) - 1$ new colors (respectively, $\eta(\mathcal{P}([P_n]^2)) - 1$ new colors). Thus $\eta(\mathcal{E}([P_n \square C_m]^2)) \le \chi'(P_n) + \chi'(C_m) - 1$ (case (b)) (respectively, $\eta(\mathcal{P}([P_n \square C_m]^2)) \le \eta(\mathcal{P}([P_n]^2)) + \eta(\mathcal{P}([C_m]^2)) - 1$ (case (f))). □

We can determine the number of colors needed for the edge set $\mathcal{E}([P_n \square C_m]^2)$ and for the power edges of $[P_n \square C_m]^2$.

**Lemma 3.1.** Let $P_n$ and $C_m$ be respectively a path of order $n \ge 2$ and a cycle of order $m \ge 3$. Then

$$ \eta(\mathcal{E}([P_n \square C_m]^2)) \le \begin{cases} 3 & \text{if } n = 2, \\ 4 & \text{otherwise.} \end{cases} $$

**Proof.** Results are deduced from Property 3.1 and Fact 3.1. □

**Lemma 3.2.** Let $P_n$ and $C_m$ be respectively a path of order $n \ge 2$ and a cycle of order $m \ge 3$. Then

$$ \eta(\mathcal{P}([P_n \square C_m]^2)) \le \begin{cases} 0 & \text{if } n = 2 \text{ and } m = 3, \\ \eta(\mathcal{P}([C_m]^2)) & \text{if } n = 2, \text{ and } m \ne 3, \\ \eta(\mathcal{P}([P_n]^2)) & \text{if } n \ne 2, \text{ and } m = 3, \\ 2 & \text{if } 3 \le n \le 4 \text{ and } m = 4, \\ 3 & \text{if } 3 \le n \le 4 \text{ and } m > 4 \text{ or } n \ge 5 \text{ and } m = 4, \\ 4 & \text{otherwise.} \end{cases} $$

**Proof.** Results are deduced from Property 3.1 and Propositions 3.1 and 3.2. □

Now, we examine the cross edges of $[P_n \square C_m]^2$.

**Lemma 3.3.** Let $P_n$ and $C_m$ be respectively a path of order $n \ge 3$ and a cycle of order $m \ge 3$. Then $\eta(\mathcal{E}([P_n \square C_m]^2)) \le 4$.

**Proof.** Note that the cross edges between two consecutive copies $C_m^j$ and $C_m^{j+1}$ form either two independent cycles of order $m$ if $m$ is even, or a cycle of order $2m$ if $m$ is odd. Each of these graphs is colorable with two colors by Fact 3.1 (note that if $m$ is even, the two cycles are colored with the same two colors). Moreover, the cross edges between $C_m^j$ and $C_m^{j+1}$ and between $C_m^{j+1}$ and $C_m^{j+2}$ have common vertices and need different colorings. Thus we color cross edges between $C_m^j$ and $C_m^{j+1}$, for $1 \le j \le n - 1$, with two colors when $j$ is odd and with two other colors when $j$ is even. Cross edges are then colored with at most four colors. □
**Corollary 3.1.** Let $P_2$ and $C_m$ be respectively a path of order 2 and a cycle of order $m \ge 3$. Then $\eta(\mathscr{C}([P_2 \square C_m]^2)) \le 2$.

**Proof.** Since only two copies of $C_m$ exist, we deduce from Lemma 3.3 that only two colors are sufficient to color $\mathscr{C}([P_2 \square C_m]^2)$. □

Finally, we evaluate the chromatic index of the square of cylindrical grids. First, note that since for any graph $G$, $\chi'(G) \ge \Delta(G)$, then for any cylindrical grid $G \equiv P_n \square C_m$ (where $n \ge 2$ and $m \ge 3$), Lemmas 3.1, 3.2, 3.3, and Corollary 3.1 give the following inequality (where $\eta(E([G]^2)) = \eta(\mathscr{E}([G]^2)) + \eta(\mathscr{P}([G]^2)) + \eta(\mathscr{C}([G]^2))$),

$$ \Delta([G]^2) \le \chi'([G]^2) \le \eta(E([G]^2)). \quad (1) $$

**Theorem 3.1.** Let $P_n$ and $C_m$ be respectively a path of order $n \ge 2$ and a cycle of order $m \ge 3$. Then

$$ \chi'([P_n \square C_m]^2) = \left\{ \begin{array}{ll} 5 & \text{if } n=2 \text{ and } m=3, \qquad (a) \\ 6 & \text{if } n=2 \text{ and } m=4, \qquad (b) \\ 7 & \text{if } n=2 \text{ and } m \ge 5, \qquad (c) \\ 8 & \text{if } n=m=3 \qquad (d) \\ 9 & \text{if } n=3 \text{ and } m=4, \text{ or } n=4 \text{ and } m=3, \qquad (e) \\ 10 & \text{if } n=3 \text{ and } m \ge 5, \text{ or } n=m=4, \text{ or } n \ge 5 \text{ and } m=3, \qquad (f) \\ 11 & \text{if } n=4 \text{ and } m \ge 5, \text{ or } n \ge 5 \text{ and } m=4, \qquad (g) \\ 12 & \text{otherwise.} \qquad (h) \end{array} \right. $$

**Proof.** The results are mainly deduced from inequality (1) using the maximum degree of the graph and the preliminary lemmas. However, for particular cases, we propose specific colorings to prove the upper bounds.

If $n=2$ and $m=3$ (case (a)), then $[P_n \square C_m]^2 \equiv K_6$, the complete graph of order 6 and it is known that $\chi'(K_6) = 5$.

For cases (b), (g), and (h), we have respectively $\Delta([P_2 \square C_4]^2) = 6$, $\Delta([P_n \square C_m]^2) = 11$ and $\Delta([P_n \square C_m]^2) = 12$. Moreover, Lemmas 3.1, 3.2, 3.3, and Corollary 3.1 give respectively $\eta(E([P_2 \square C_4]^2)) \le 3+1+2=6$, $\eta(E([P_n \square C_m]^2)) \le 4+3+4=11$ and $\eta(E([P_n \square C_m]^2)) \le 4+4+4=12$. Therefore, by inequality (1), the results hold.

Case (c). First, note that $\Delta([P_2 \square C_m]^2) = 7$ for $m \ge 5$. We propose a coloring $c$ of the graph to show that $\eta(E([P_n \square C_m]^2)) \le 7$. We start by coloring the edges $\mathscr{E}([P_n \square C_m]^2)$ and $\mathscr{P}([P_n \square C_m]^2)$. We use the same coloring on the two copies $C_m^1$ and $C_m^2$. If $m$ is even, color each copy $C_m^i$ with the two colors $\{1, 2\}$ and by Lemma 3.2, edges of $\mathscr{P}([C_m^i]^2)$ need three colors to be properly colored, called $\{3, 4, 5\}$. If $m$ is odd, then for each copy $C_m^i$, color the induced subpath $P_m = \{x_1, x_2, \dots, x_m\}$ with colors $\{1, 2\}$, and color the edge $x_1x_m$ with the color 3. Note that edges of $\mathscr{P}([C_m^i]^2)$ form an odd cycle of order $m$. Color edges $x_1x_{m-1}$ and $x_{m-2}x_m$ with color 5, and edge $x_2x_m$ with color 4, thus all incident edges to vertices $x_1$ (respectively, $x_m$) have different colors. Then, for any $1 \le i \le m-3$, put $c(x_ix_{i+2}) = 4$ if $i \bmod 4 = \{0, 1\}$ and $c(x_ix_{i+2}) = 3$ if $i \bmod 4 = \{2, 3\}$. Thus, $\mathscr{P}([C_m^i]^2)$ is properly colored and no conflict is introduced with the coloring of $\mathscr{E}([P_n \square C_m]^2)$. Figure 3.1 illustrates the colorings of $[C_m]^2$. In both cases, note that for the copies of $P_2$ each edge $x_{i,1}x_{i,2}$, with $1 \le i \le m$, has incident edges from copies of $C_m$ colored with only four different colors (the same colors for each endvertex since the coloring is the same for every copy $C_m^i$). Thus each edge $x_{i,1}x_{i,2}$ can be properly colored with an already used color and edges $\mathscr{E}([P_n \square C_m]^2) \cup \mathscr{P}([P_n \square C_m]^2)$ are colored with five colors. Since Corollary 3.1 shows that two colors are sufficient to color the cross edges, then $\eta(E([P_n \square C_m]^2)) \le 7$ and the result is given by inequality (1).

Case (d). Figure 3.2 proposes a proper edge 8-coloring for the graph $[P_3 \square C_3]^2$. Moreover, since $\Delta([P_3 \square C_3]^2) = 8$ inequality (1) gives the result.

Case (e). If $n=4$ and $m=3$, then $\Delta([P_4 \square C_3]^2) = 9$. Since Lemmas 3.1, 3.2 and 3.3 give $\eta(E([P_n \square C_m]^2)) \le 9$, we deduce the result from inequality (1). Consider $n=3$ and $m=4$. Figure 3.3 gives a proper edge 9-coloring for the graph $[P_3 \square C_4]^2$. Moreover, since $\Delta([P_3 \square C_4]^2) = 9$, we deduce the result from inequality (1) too.

Case (f). For every subcase note that $\Delta([P_n \square C_m]^2) = 10$. If $n=m=4$ or $n \ge 5$ and $m=3$, then Lemmas 3.1, 3.2, and 3.3 give $\eta(E([P_n \square C_m]^2)) \le 10$, and by inequality (1) the results hold. Consider $n=3$ and $m \ge 5$. We propose a construction to color the squared grid $[P_n \square C_m]^2$ with ten colors:

* Cross edges $\mathscr{C}([P_3 \square C_m]^2)$. By Lemma 3.3, four colors are needed to color cross edges (two colors for edges between copies $C_m^1$ and $C_m^2$, denoted by $\{7, 8\}$, and two colors for edges between copies $C_m^2$ and $C_m^3$, denoted by $\{9, 10\}$).

* Edges $\mathscr{E}([C_m^i]^2)$ and power edges $\mathscr{P}([C_m^i]^2)$, $1 \le i \le 3$. We adapt the coloring $c$ described in case (c). For edges $\mathscr{E}([C_m^i]^2)$, use the same coloring as $c$ with colors $\{1, 2\}$ or $\{1, 2, 3\}$ according to the parity of $m$. For edges $\mathscr{P}([C_m^i]^2)$ we distinguish two subcases. Edges $\mathscr{P}([C_m^2]^2)$ are directly colored as in $c$ with colors $\{3, 4, 5\}$. For power edges $\mathscr{P}([C_m^1]^2)$ (respectively, $\mathscr{P}([C_m^3]^2)$), use the coloring $c$ but replace the set of colors $\{3, 4, 5\}$ by the set $\{9, 10, 5\}$ (respectively, $\{7, 8, 5\}$). Note that this partial coloring is proper since copy $[C_m^1]^2$ (respectively, $[C_m^3]^2$) does not share vertices with copies $[C_m^2]^2$ and $[C_m^3]^2$ (respectively, $[C_m^1]^2$ and $[C_m^2]^2$) and the colors used for cross edges can be reused.
• Edges $\mathcal{E}([P_3^j]^2)$, $1 \le j \le m$. We start by coloring every edge $x_{j,1}x_{j,2}$. Note that its endvertices have incident edges colored with at most four different colors in $\{1, 2, \dots, 5\}$ (each of them with two neighbors in $\mathcal{E}([C_3^i]^2)$ with the same colors and two neighbors in $\mathcal{P}([C_3^i]^2)$ with the same colors or colors with a number larger than 5, $1 \le i \le 2$). Thus these edges can be properly colored without introducing a new color. Then we color the edges $x_{j,2}x_{j,3}$ with the same new color, denoted by 6 (since they are independent). Thus, the partial coloring remains proper.

• Power edges $\mathcal{P}([P_3^j]^2)$, $1 \le j \le m$. These edges connect vertices of copies $[C_m^1]^2$ and $[C_m^3]^2$. Vertices of these copies have degree 8 and every edge $x_{j,1}x_{j,3}$ admits 15 incident edges. Since colorings of $\mathcal{E}([C_m^i]^2)$ are the same, and since the four colors of cross edges are reused in the colorings of $\mathcal{P}([C_m^1]^2)$ and $\mathcal{P}([C_m^3]^2)$, every edge $x_{j,1}x_{j,3}$ is adjacent to at most 9 colors (4 from cross edges, 4 from $\mathcal{E}([P_n \square C_m]^2)$ and at most one more from power edges). Since the partial coloring uses 10 colors, each edge $x_{j,1}x_{j,3}$ can be properly colored without introducing new colors.

Thus the coloring of the graph is proper with ten colors. Therefore $\eta(E([P_n \square C_m]^2)) \le 10$ and the result holds. Figure 3.4 presents an example of the above proper edge 10-coloring for $[P_3 \square C_m]^2$ when $m$ is odd. $\square$

**Corollary 3.2.** *The squared cylindrical grid $[P_n \square C_m]^2$, with $n \ge 2$ and $m \ge 3$, is a class one graph.*

**Proof.** Theorem 3.1 shows $\chi'([P_n \square C_m]^2) = \Delta([P_n \square C_m]^2)$. $\square$

<figure><img src="image_3.png" /><figcaption>**Figure 3.1:** An edge coloring of $[C_m^i]^2$ according to the parity of $m$, with $1 \le i \le 2$ (Theorem 3.1 case (c)).</figcaption></figure>

<figure><img src="image_4.png" /><figcaption>**Figure 3.2:** A proper edge 8-coloring of $[P_3 \square C_3]^2$.</figcaption></figure>
<figure><img src="image_5.png" /><figcaption>Figure 3.3: A proper edge 9-coloring of $[P_3 \square C_4]^2$.</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>Figure 3.4: A proper edge 10-coloring of $[P_3 \square C_m]^2$, with $m \ge 5$ odd.</figcaption></figure>

## 4. The $[r, s, t]$-coloring of $[P_n \square C_m]^2$

From Theorem 1.1 we see that upper and lower bounds are based on the chromatic number and chromatic index of the considered graph. Thus we can deduce the following corollary.

**Corollary 4.1.** Let $P_n$ and $C_m$ be respectively a path and a cycle of orders $n \ge m \ge 3$. For the cylindrical grid $G = P_n \square C_m$, we have

$$ \max\{r(\chi([G]^2) - 1) + 1, s(\chi'([G]^2) - 1) + 1, t + 1\} \le \chi_{r,s,t}([G]^2) \le 4r + 11s + t + 1. $$

**Proof.** Follows from Theorems 1.1, 1.2 and 3.1.

<figure><img src="image_7.png" /></figure>

These bounds seem large, but next, we show that under conditions on $r$, $s$, and $t$, the lower and the upper bounds are reachable. We first prove that the upper bound is reached for $r = s = t = 1$.
**Theorem 4.1.** Let $P_n$ and $C_m$ be respectively a path and a cycle of orders $n \ge 7$ and $m \ge 7$ respectively, where $m \ne 0 (\text{mod } 5)$. Then

$$ \chi_{1,1,1}([P_n \square C_m]^2) = 4r + 11s + t + 1 = 17. $$

**Proof.** Let $k = 4r + 11s + t + 1 = 17$. Corollary 4.1 gives $\chi_{1,1,1}([P_n \square C_m]^2) \le k$. Suppose there exists a $[r, s, t]$-coloring of $[P_n \square C_m]^2$ with $k' < k$ colors. We can see that the graph $G'$ depicted in Figure 4.1 is an induced subgraph of $[P_n \square C_m]^2$. Without loss of generality (w.l.o.g.), choose the subgraph among copies $P_n^3, P_n^4, \dots, P_n^{m-2}$ and $C_m^3, C_m^4, \dots, C_m^{n-2}$. Thus every

<figure><img src="image_8.png" /><figcaption>**Figure 4.1:** A subgraph $G'$ of $[P_n \square C_m]^2$ (dashed edges are added by the power 2).</figcaption></figure>

vertices of $G'$ has a degree 12 in $[P_n \square C_m]^2$. Theorem 3.1 (case (h)) gives an edge coloring with 12 colors for $[P_n \square C_m]^2$ and every vertex of $G'$ is adjacent to the twelve colors. Since $t = 1$, these colors cannot be used for a proper coloring of the vertices of $G'$. Thus these vertices are colored with $k' - 12 < 5$ colors. A proper coloring of them implies $c(a) \ne c(b)$, $c(b) \ne c(c)$ and $c(a) \ne c(c)$ (w.l.o.g., assume that $a, b, c$ are colored respectively with colors 1, 2, 3). Since $e$ is adjacent to $a, b$ and $c$, $c(e) = 4$. To have a proper coloring we need to have $c(d) = c(c) = 3$ and $c(f) = c(a) = 1$. Thus, vertex $g$ is adjacent to four colors and needs a new color, which contradicts the number of colors and $\chi_{1,1,1}([P_n \square C_m]^2) \ge k$. Therefore $\chi_{1,1,1}([P_n \square C_m]^2) = 17$. $\square$

Next, we present some cases for which the lowest value of the $[r, s, t]$-chromatic number is reached.

**Theorem 4.2.** Let $P_n$ and $C_m$ be respectively a path and a cycle of orders $n \ge m \ge 5$, where $m \ne 0 (\text{mod } 5)$. If $r \ge 2s + 2t$ and $s \le 2t$, then

$$ \chi_{r,s,t}([P_n \square C_m]^2) = r(\chi([P_n \square C_m]^2) - 1) + 1 = 4r + 1. $$

**Proof.** Note that $r \ge 2t + 2s \ge 3s$. Thus we have $4r \ge 12s$ and by Corollary 4.1 and Theorem 1.2 we have $\chi_{r,s,t}([P_n \square C_m]^2) \ge \max\{r(\chi([P_n \square C_m]^2) - 1) + 1, 11s + 1, t + 1\} = r(\chi([P_n \square C_m]^2) - 1) + 1 = 4r + 1$.

We define the two sets of colors $S_v = \{0, r, 2r, 3r, 4r\}$ for the vertices and $S_e = \bigcup_{i=0}^3 S_e^i$ for the edges where $S_e^i = \{ir + t, ir + t + s, ir + t + 2s\}$. We have $|S_v| = 5$ and $|S_e| = 12$. Theorems 1.2 and 3.1 show that $[P_n \square C_m]^2$ needs at least five colors on its vertices and twelve colors on its edges. Thus these theorems give a coloring of the graph with the colors of $S_v$ and $S_e$ respectively. We need to verify that these colors respect the $r$-, $s$- and $t$-conditions of a $[r, s, t]$-coloring. Figure 4.2 shows the sets of colors and the color distances between these colors to check the conditions.

<figure><img src="image_9.png" /><figcaption>**Figure 4.2:** Set of colors used in $S_v$ and $S_e$ (Theorem 4.2) and the color distances between them on dashed lines (note that $\alpha = r - 2s \ge 2t \ge s$ and $\beta = r - 2s - t \ge t$).</figcaption></figure>

In $S_v$ the $r$-condition is clearly fulfilled. Moreover, in every $S_e^i$, the colors fulfill the $s$-condition. And since the color difference between two consecutive sets $S_e^{i-1}$ and $S_e^i$ is at least $\alpha = [ir + t] - [(i-1)r + t + 2s] = r - 2s$, for any $1 \le i \le 3$, we have $\alpha = r - 2s \ge 2t \ge s$ and the $s$-condition is fulfilled between the sets $S_e^i$ (and so in $S_e$). Finally, since $\beta = [ir] - [(i-1)r + t + 2s] = r - 2s - t$, for any $1 \le i \le 3$, we have $\beta = r - 2s - t \ge t$ and the $t$-condition is also fulfilled between colors of $S_v$ and $S_e$. Thus the coloring is a $[r, s, t]$-coloring and we deduce $\chi_{r,s,t}([P_n \square C_m]^2) \le 4r + 1$. Therefore $\chi_{r,s,t}([P_n \square C_m]^2) = 4r + 1$. $\square$

**Corollary 4.2.** Let $P_n$ and $C_m$ be respectively a path and a cycle of orders $n \ge m \ge 5$, where $m \ne 0 (\text{mod } 5)$. If $r \ge 3s$ and $s \ge 2t$, then $\chi_{r,s,t}([P_n \square C_m]^2) = 4r + 1$.

**Proof.** The proof is similar to Theorem 4.2. Use the coloring given in Theorem 4.2. Since $\alpha = r - 2s \ge s$ and $\beta = r - 2s - t \ge s - t \ge t$, for any $1 \le i \le 3$, we can see, as in Theorem 4.2, that the $r$-, $s$- and $t$-conditions are fulfilled in the coloring and $\chi_{r,s,t}([P_n \square C_m]^2) = 4r + 1$. $\square$
**Theorem 4.3.** Let $P_n$ and $C_m$ be respectively a path and a cycle of orders $n \ge 2$ and $m \ge 3$, where $m \ne 0 \pmod 5$. If $s \ge 2t$ and $s \ge r$, then

$$ \chi_{r,s,t}([P_n \square C_m]^2) = (\chi'([P_n \square C_m]^2) - 1)s + 1. $$

**Proof.** Since $s \ge r$, we have $(\chi'([P_n \square C_m]^2) - 1)s \ge 4r$ (by Theorem 1.2). Moreover, since $s \ge 2t$ then Corollary 4.1 gives $\chi_{r,s,t}([P_n \square C_m]^2) \ge \max\{4r+1, (\chi'([P_n \square C_m]^2) - 1)s + 1, t+1\} = (\chi'([P_n \square C_m]^2) - 1)s + 1$.

Let $k = \chi'([P_n \square C_m]^2) - 1$. Then we define the two sets of colors $S_v = \{t, s+t, 2s+t, 3s+t, 4s+t\}$ and $S_e = \{0, s, 2s, \dots, ks\}$. Thus $|S_v| = 5$ and $|S_e| = k+1$. Theorems 1.2 and 3.1 show that $[P_n \square C_m]^2$ needs at least $|S_v|$ colors on its vertices and $|S_e|$ colors on its edges. Thus these theorems give a coloring of the graph with the colors of $S_v$ and $S_e$ respectively. We need to verify that these colors respect the $r$-, $s$- and $t$-conditions of a $[r, s, t]$-coloring. Figure 4.3 shows the sets of colors and the color distances between these colors to check the conditions.

<figure><img src="image_10.png" /><figcaption>**Figure 4.3:** Set of colors used in $S_v$ and $S_e$ (Theorem 4.3) and the color distances between them on dashed lines (note that $\alpha = s \ge r$ and $\beta = s - t \ge t$).</figcaption></figure>

In $S_e$ the $s$-condition is obviously fulfilled. Then for the set $S_v$, since $s \ge r$, the $r$-condition is fulfilled too. Finally, since the color difference between colors of $S_v$ and $S_e$ is at least $\beta = s - t \ge t$, the $t$-condition is fulfilled too. Thus the coloring is a $[r, s, t]$-coloring and we deduce $\chi_{r,s,t}([P_n \square C_m]^2) \le ks + 1$. Therefore $\chi_{r,s,t}([P_n \square C_m]^2) = (\chi'([P_n \square C_m]^2) - 1)s + 1$. □

# 5. Conclusion

In this paper, we considered the square of the Cartesian product of a path by a cycle. We presented the chromatic index of such a graph. In particular, we proved that this class of graphs is of class one according to Vizing's theorem since its chromatic index is $\Delta$, the maximum degree of the graph. We also presented the bounds for the $[r, s, t]$-chromatic number of squared cylindrical grids and proved they are tight. We proposed values of $r, s$, and $t$ for which the exact value of the $[r, s, t]$-chromatic number is given.

# Acknowledgment

The author thanks the referees for their valuable remarks that improved the clarity of the article.

# References

[1] M.S. Cavers, K. Seyffarth, E.P. White, Distinguishing chromatic number of complements of Cartesian products of complete graphs, Discrete Math. 341 (2018) 2431–2441.

[2] S.-H. Chiang, J.-H. Yan, On $L(d, 1)$-labeling of Cartesian product of a cycle and a path, Discrete Appl. Math. 156 (2008) 2867–2881.

[3] L. Dekar, B. Effantin, H. Kheddouci, $[r, s, t]$-coloring of trees and bipartite graphs, Discrete Math. 310 (2010) 260–269.

[4] L. Dekar, B. Effantin, H. Kheddouci, $[r, s, t]$-coloring of graph products, Graphs Combin. 30(5) (2014) 1135–1147.

[5] Z. Dvořák, D. Král', P. Nejedlý, R. Škrekovski, Coloring squares of planar graphs with girth six, European J. Combin. 29(4) (2008) 838–849.

[6] M. Jakovac, Y. Otaghi, On the security number of the Cartesian product of graphs, Discrete Appl. Math. 304 (2021) 119–128.

[7] A. Kemnitz, J. Lehmann, $[r, s, t]$-Colorings of Stars, Congr. Numer. 185 (2007) 65–80.

[8] A. Kemnitz, M. Marangio, $[r, s, t]$-Colorings of graphs, Discrete Math. 307 (2007) 199–207.

[9] K. M. Koh, K. W. Soh, Power domination of the cartesian product of graphs, AKCE Int. J. Graphs Comb. 13 (2016) 22–30.

[10] N. Mandal, P. Panigrahi, $L(2, 1)$-colorings and Irreducible No-hole Colorings of Cartesian Product of Graphs, Electron. Notes Discrete Math. 63 (2017) 343–352.

[11] M. Molloy, M. R. Salavatipour, A bound of the chromatic number of the square of a planar graph, J. Combin. Theory Ser. B 94(2) (2005) 189–213.

[12] Z. Shao, A. Vesel, A note on the chromatic number of the square of Cartesian product of two cycles, Discrete Math. 313 (2013) 999–1001.

[13] E. Sopena, J. Wu, Coloring the square of Cartesian product of two cycles, Discrete Math. 310 (2010) 2327–2333.

[14] C. Thomassen, The square of a planar cubic graph is 7-colorable, J. Combin. Theory Ser. B 128 (2018) 192–218.

[15] J. van den Heuvel, S. McGuinness, Coloring the square of a planar graph, J. Graph Theory 42(2) (2002) 110–124.

[16] M. S. Villá, $[r, s, t]$-Colourings of Paths, Cycles and Stars, Doctoral Thesis, TU Bergakademie, Freiberg, 2005.

[17] M. S. Villá, I. Schiermeyer, $[r, s, t]$-Colorings of paths, Opuscula Math. 27(1) (2007) 131–149.

[18] B. Xue, L. Zuo, G. Li, Coloring of the Square of Sierpiński Graphs, Graphs Combin. 31(5) (2015) 1795–1805.