Injective Coloring of Product Graphs

Abstract

The problem of injective coloring in graphs can be revisited through two different approaches: coloring the two-step graphs and vertex partitioning of graphs into open packing sets, each of which is equivalent to the injective coloring problem itself. Taking these facts into account, we observe that the injective coloring lies between graph coloring and domination theory. We make use of these three points of view in this paper so as to investigate the injective coloring of some well-known graph products. We bound the injective chromatic number of direct and lexicographic product graphs from below and above. In particular, we completely determine this parameter for the direct product of two cycles. We also give a closed formula for the corona product of two graphs.

1 Introduction

Throughout this paper, we consider G as a finite simple graph with vertex set V(G) and edge set E(G). The open neighborhood of a vertex v is denoted by $N_{G}(v)$, and its closed neighborhood is $N_{G}[v]=N_{G}(v)\cup \{v\}$. The minimum and maximum degrees of G are denoted by $\delta (G)$ and $\Delta (G)$, respectively. Given the subsets $A,B\subseteq V(G)$, by [A, B], we mean the set of edges with one end point in A and the other in B. Finally, for a given set $S\subseteq V(G)$, by G[S] we represent the subgraph of G induced by S (that is, the subgraph of G with vertex set S in which two vertices are adjacent if they are adjacent in G). We use [30] as a reference for terminology and notation which are not explicitly defined here.

1.1 Main Terminology

For all four standard products of graphs G and H (according to [10]), the vertex set of the product is $V(G)\times V(H)$. Their edge sets are defined as follows.

• In the Cartesian product $G\square H$, two vertices are adjacent if they are adjacent in one coordinate and equal in the other.

• In the direct product $G\times H$ two vertices are adjacent if they are adjacent in both coordinates.

• The edge set of the strong product $G\boxtimes H$ is the union of $E(G\square H)$ and $E(G\times H)$.

• Two vertices (g, h) and $(g',h')$ are adjacent in the lexicographic product $G\circ H$ if either $gg'\in E(G)$ or “$g=g'$ and $hh'\in E(H)$.”

Note that all these four products are associative, and only the first three ones are commutative (see [10]).

Letting G and H be graphs and $V(G)=\{v_1,\ldots ,v_{n}\}$, the corona product $G\odot H$ of graphs G and H is obtained from the disjoint union of G and n disjoint copies of H, say $H_1,\ldots , H_{n}$, such that the vertex $v_i\in V(G)$ is adjacent to every vertex of $H_i$ for all $i\in \{1,\dots ,n\}$.

A function $f:V(G)\rightarrow \{1,\dots ,k\}$ is an injective k-coloring function if no vertex v is adjacent to two vertices u and w with $f(u)=f(w)$. For such a function f, the set of color classes $\big \{\{v\in V(G)\mid f(v)=i\}\big \}_{1\le i\le k}$ is an injective k-coloring of G (or simply an injective coloring if k is clear from the context). The minimum k for which a graph G admits an injective k-coloring is the injective chromatic number $\chi _{i}(G)$ of G. Injective colorings were introduced in [11], and further studied in [3, 17, 24, 27] for just some examples.

Another approach to the injective coloring of graphs, which is indeed previous to the idea of injective colorings, can be presented as follows. The two-step graph $\mathcal {N}(G)$ of a graph G is the graph having the same vertex set as G with an edge joining two vertices in $\mathcal {N}(G)$ if and only if they have a common neighbor in G. These graphs were introduced in [1] and investigated later in [4, 8, 22]. Since a vertex subset S is independent in $\mathcal {N}(G)$ if and only if every two vertices of S have no common neighbor in G, we readily observe that

$$\begin{aligned} \chi _{i}(G)=\chi \big (\mathcal {N}(G)\big ), \end{aligned}$$

(1)

in which $\chi$ is the well-known chromatic number. This exposition is centered into giving some contributions to the injective coloring of graph products.

1.2 Related Concepts and Plan of the Article

This subsection is devoted to showing some strong relationships between the above-mentioned concept and other ones related to domination theory. A subset $S\subseteq V(G)$ is a dominating set (resp. total dominating set) if each vertex in $V(G)\backslash S$ (resp. V(G)) has at least one neighbor in S. The domination number $\gamma (G)$ (resp. total domination number $\gamma _{t}(G)$) is the minimum cardinality among all dominating sets (resp. total dominating sets) in G. For more information on domination theory, the reader can consult [13, 14].

The study of distance coloring of graphs was initiated by Kramer and Kramer [20, 21] in 1969. A 2-distance coloring (or, 2DC for short) of a graph G is a mapping of V(G) to a set of colors (nonnegative integers) by which any two vertices at distance at most two receive different colors. The minimum number of colors k for which there is a 2DC of G is called the 2-distance chromatic number $\chi _{2}(G)$ of G.

By a $\chi _{i}(G)$-coloring and a $\chi _{2}(G)$-coloring, we mean an injective coloring and a 2DC of G of cardinality $\chi _{i}(G)$ and $\chi _{2}(G)$, respectively.

On the other hand, problems regarding vertex partitioning are classical in graph theory. In fact, there are many different ways for such partitioning into sets satisfying a specific property. For instance, when dealing with “domination” (resp. “total domination”), the problem of finding the maximum cardinality of a vertex partition of a graph G into dominating sets (resp. total dominating sets) has been widely investigated in the literature. The study of the associated parameter, called domatic number d(G) (resp. total domatic number $d_{t}(G)$), was first carried out in [7] (resp. [6]), see also the books [12, 13]. Also, a topic connected to domination is that one of packings. Based on such close relationships, one would find interesting to consider graph partitioning problems regarding packing sets. In this concern, a subset $B\subseteq V(G)$ is called a packing (or a packing set) in G if for each distinct vertices $u,v\in B$, $N_{G}[u]\cap N_{G}[v]=\emptyset$ (equivalently, B is a packing in G if $|N_{G}[v]\cap B|\le 1$ for all $v\in B$). The packing number $\rho (G)$ is the maximum cardinality among all packing sets in G. In connection with this, a vertex partition ${\mathbb {P}}=\{P_{1},\dots ,P_{|{\mathbb {P}}|}\}$ of a graph G is called a packing partition if $P_{i}$ is a packing in G for each $1\le i\le |{\mathbb {P}}|$. The packing partition number p(G) is the minimum cardinality among all such partitions of G.

In contrast with the construction of $\mathcal {N}(G)$ for a graph G, the closed neighborhood graph $\mathcal {N}_{c}(G)$ of a graph G has vertex set V(G), and two distinct vertices u and v are adjacent in $\mathcal {N}_{c}(G)$ if and only if $N_{G}[u]\cap N_{G}[v]\ne \emptyset$ (see [2]). With this in mind, we observe that a 2DC of a graph G is the same as a coloring of its closed neighborhood graph. It is also easily seen that $\mathcal {N}_{c}(G)$ is isomorphic to the square $G^{2}$ of G. We, in addition, note that the 2DC problem is equivalent to the problem of vertex partitioning of a graph into packings. Therefore, we altogether observe that

$$\begin{aligned} \chi _{2}(G)=\chi (G^{2})=\chi \big (\mathcal {N}_{c}(G)\big )=p(G). \end{aligned}$$

(2)

A natural situation, concerning domination and packings, comes across while considering the study of related parameters in which open neighborhoods are used, instead of closed neighborhoods. Indeed, a subset $B\subseteq V(G)$ is said to be an open packing (or an open packing set) in G if for any distinct vertices $u,v\in B$, $N_{G}(u)\cap N_{G}(v)=\emptyset$. The open packing number, denoted by $\rho _{o}(G)$, is the maximum cardinality among all open packing sets in G (see [15]).

Motivated by the existence of packing partitions and open packing sets, we might say that a vertex partition ${\mathbb {P}}=\{P_{1},\dots ,P_{|{\mathbb {P}}|}\}$ of a graph G is an open packing partition (OPP for short) if $P_{i}$ is an open packing in G for each $1\le i\le |{\mathbb {P}}|$. The open packing partition number $p_{o}(G)$ is the minimum cardinality among all OPPs of G. In this paper, we investigate this kind of vertex partitioning of graphs. However, it turns out that such partitions can be considered from other approaches since we readily observe that for any k-injective coloring function f, the partition $\big \{\{v\in V(G)\mid f(v)=i\}\big \}_{1\le i\le k}$ forms an OPP of G and vice versa. This fact, together with (1) and the idea of two-step graphs, leads to

$$\begin{aligned} \chi _{i}(G)=\chi \big (\mathcal {N}(G)\big )=p_{o}(G), \end{aligned}$$

(3)

which is an open analog of (2). This establishes another relationship between graph coloring and domination theory. In connection with this, we next give some contributions to the injective chromatic number (or OPP number) of graphs (or equivalently, to the chromatic number of two-step graphs) with emphasis on graph products. In this sense, from now on, we indistinctively use the three terminologies in concordance with the best use in each situation.

This paper is organized as follows. We consider the direct, lexicographic and corona products in order to study $\chi _{i}(G*H)$ in general case, in which $*\in \{\times ,\circ ,\odot \}$ (here $\odot$ represents the corona product, which is not exactly a standard product as defined in [10], but it can be taken more as a graph operation). Sharp lower and upper bounds are exhibited on the injective chromatic number when dealing with the direct and lexicographic product graphs. In the case of corona product graphs, we give a closed formula for this parameter and prove that it assumes all values given in the formula. In particular, a counterexample to a formula given in [9] concerning the 2-distance chromatic number of lexicographic product graphs is presented. Moreover, when dealing with the direct product graphs, we completely determine the injective chromatic number of direct product of two cycles by using the new tools given in this paper and some classical results in the literature.

We end this section by a remark. Let $u\in V(G)$ be a vertex of maximum degree and let ${\mathbb {B}}=\{B_{1},\dots ,B_{\chi _{i}(G)}\}$ be a $\chi _{i}(G)$-coloring. Because $B_{j}$ is an open packing in G for each $1\le j\le \Delta (G)$, u has at most one neighbor in $B_{j}$ and hence $\sum _{j=1}^{\chi _{i}(G)}|N(u)\cap B_{j}|\le \chi _{i}(G)$. So,

$$\begin{aligned} \chi _{i}(G)\ge \Delta (G). \end{aligned}$$

(4)

This simple but important inequality will turn out to be useful in some places in this paper.

2 Direct Product Graphs

2.1 General Case

We here bound the injective chromatic number of direct product graphs from above and below. To this end, given two graphs G and H defined on the same vertex set, by $G\sqcup H$, we mean the graph with vertex set $V(G\sqcup H)=V(G)=V(H)$ and edge set $E(G\sqcup H)=E(G)\cup E(H)$. We assume that $I_{G}$ and $I_{H}$ are the sets of isolated vertices of G and H, respectively. Let $G^{-}$ and $H^{-}$ be the graphs obtained from G and H by removing all isolated vertices from G and H, respectively. Moreover, by $G+H$ we represent the disjoint union of two graphs G and H.

We proceed with the following lemma which will have important roles throughout this section.

Lemma 1

Let G and H be any graphs. Then,

$$\begin{aligned} \mathcal {N}(G\times H)\cong \big (\mathcal {N}(G^{-})\boxtimes \mathcal {N}(H^{-})\big )^{-}+\overline{K_{p}}, \end{aligned}$$

in which p is the cardinality of

$$\begin{aligned} \begin{array}{lcl} I_{\mathcal {N}(G\times H)}=\{(g,h)\in V(G)\times V(H)\mid \\ \hbox {for each }(g',h')\in V(G)\times V(H), N_{G}(g)\cap N_{G}(g')=\emptyset \hbox { or }N_{H}(h)\cap N_{H}(h')=\emptyset \}. \end{array} \end{aligned}$$

Proof

It is readily observed that

$$\begin{aligned} \begin{array}{lcl} \{(g,h)\in V(G)\times V(H)\mid \\ \hbox {for each }(g',h')\in V(G)\times V(H), N_{G}(g)\cap N_{G}(g')=\emptyset \hbox { or }N_{H}(h)\cap N_{H}(h')=\emptyset \} \end{array} \end{aligned}$$

is the set of isolated vertices of $\mathcal {N}(G\times H)$. We next recall that

$$\begin{aligned} \mathcal {N}(G^{-})\boxtimes \mathcal {N}(H^{-})=\big (\mathcal {N}(G^{-})\times \mathcal {N}(H^{-})\big )\sqcup \big (\mathcal {N}(G^{-})\square \mathcal {N}(H^{-})\big ). \end{aligned}$$

Let $(g,h)(g',h')$ be an edge in $\mathcal {N}(G\times H)^{-}$. By symmetry, we may assume that $h\ne h'$. Therefore, there exists a vertex $(g'',h'')$ adjacent to both (g, h) and $(g',h')$ in $G\times H$. This means that $g''g,g''g'\in E(G)$ and $h''h,h''h'\in E(H)$. In particular, we have $g,g',g''$ and $h,h',h''$ are vertices of $G^{-}$ and $H^{-}$, respectively. Therefore, both $N_{G^{-}}(g)\cap N_{G^{-}}(g')$ and $N_{H^{-}}(h)\cap N_{H^{-}}(h')$ are nonempty. We now have “$gg'\in E\big (\mathcal {N}(G^{-})\big )$ and $hh'\in E\big (\mathcal {N}(H^{-})\big )$” if $g\ne g'$, and “$g=g'$ and $hh'\in E\big (\mathcal {N}(H^{-})\big )$” otherwise. Consequently, $(g,h)(g',h')\in E\big (\mathcal {N}(G^{-})\times \mathcal {N}(H^{-})\big )$ if $g\ne g'$, and $(g,h)(g',h')\in E\big (\mathcal {N}(G^{-})\square \mathcal {N}(H^{-})\big )$ otherwise. Thus, $(g,h)(g',h')$ is an edge of $\mathcal {N}(G^{-})\boxtimes \mathcal {N}(H^{-})$. More precisely, $(g,h)(g',h')$ is an edge of $\big (\mathcal {N}(G^{-})\boxtimes \mathcal {N}(H^{-})\big )^{-}$.

Conversely, let $(g,h)(g',h')$ be an edge in $\big (\mathcal {N}(G^{-})\boxtimes \mathcal {N}(H^{-})\big )^{-}$. Without loss of generality, we may assume that $h\ne h'$. It is easily checked that the converse of the above implications hold. So, $(g,h)(g',h')$ is an edge of $\mathcal {N}(G\times H)^{-}$. In fact, we have proved that $E\big (\mathcal {N}(G\times H)^{-}\big )=E\big (\big (\mathcal {N}(G^{-})\boxtimes \mathcal {N}(H^{-})\big )^{-}\big )$. Now, the identity mapping $(g,h)\rightarrow (g,h)$ serves as an isomorphism between $\mathcal {N}(G\times H)^{-}$ and $\big (\mathcal {N}(G^{-})\boxtimes \mathcal {N}(H^{-})\big )^{-}$.

On the other hand, it is clear that $\mathcal {N}(G\times H)\cong \mathcal {N}(G\times H)^{-}+\overline{K_{p}}$ in which p is the cardinality of

$$\begin{aligned} I_{\mathcal {N}(G\times H)}=\{(g,h)\mid \hbox {for each }(g',h'), N_{G}(g)\cap N_{G}(g')=\emptyset \hbox { or }N_{H}(h)\cap N_{H}(h')=\emptyset \}. \end{aligned}$$

In fact, we have proved that

$$\begin{aligned} \mathcal {N}(G\times H)\cong \big (\mathcal {N}(G^{-})\boxtimes \mathcal {N}(H^{-})\big )^{-}+\overline{K_{p}}, \end{aligned}$$

as desired. $\square$

If $\{G_{1},\dots ,G_{r}\}$ and $\{H_{1},\dots ,H_{s}\}$ are the sets of components of G and H, respectively, then it is clear that $\chi _{i}(G\times H)=\sum _{i,j}\chi _{i}(G_{i}\times H_{j})$. So, we may assume that both G and H are connected. Moreover, $G\times H$ will be an empty graph if either G or H is isomorphic to $K_1$. Therefore, it only suffices to assume that $|V(G)|,|V(H)|\ge 2$.

Theorem 1

Let G and H be connected graphs of orders at least two.

(i) If one of the factors is isomorphic to $K_{2}$, then $\chi _{i}(G\times H)=\max \{\chi _{i}(G),\chi _{i}(H)\}$.

(ii) If $\Delta (G),\Delta (H)\ge 2$, then

$$\begin{aligned} \max \{\chi _{i}(G)+\Delta (H),\chi _{i}(H)+\Delta (G)\}\le \chi _{i}(G\times H)\le \chi _{i}(G)\chi _{i}(H). \end{aligned}$$

These bounds are sharp.

Proof

By using (3) and Lemma 1, we get

$$\begin{aligned} \chi _{i}(G\times H)=\chi \big (\mathcal {N}(G\times H)\big ){} & {} =\chi \Big (\big (\mathcal {N}(G^{-})\boxtimes \mathcal {N}(H^{-})\big )^{-}+\overline{K_{p}}\Big )\\{} & {} =\chi \big (\mathcal {N}(G^{-})\boxtimes \mathcal {N}(H^{-})\big ). \end{aligned}$$

Thus, we deduce that $\chi _{i}(G\times H)\le \chi \big (\mathcal {N}(G^{-})\big )\chi \big (\mathcal {N}(H^{-})\big )=\chi _{i}(G^{-})\chi _{i}(H^{-})=\chi _{i}(G)\chi _{i}(H)$ since the chromatic number of the strong product of two graphs is always at most the product of chromatic numbers of the factors (see [19]). A trivial example that shows the tightness of this upper bound is the direct product graph $K_r\times K_t$ for $r,t\ge 3$.

On the other hand, $\chi _{i}(G\times H)=\chi \big (\mathcal {N}(G^{-})\boxtimes \mathcal {N}(H^{-})\big )\ge \max \{ \chi \big (\mathcal {N}(G^{-})\big ),\chi \big (\mathcal {N}(H^{-})\big )\} =\max \{\chi _{i}(G^{-}),\chi _{i}(H^{-})\}=\max \{\chi _{i}(G),\chi _{i}(H)\}$.

If $G\cong K_2$, then $\mathcal {N}(G)$ is an empty graph and $\chi _{i}(G)=1$. Thus,

$$\begin{aligned} \chi _{i}(G\times H)=\max \{\chi _{i}(G),\chi _{i}(H)\}=\chi _{i}(G)\chi _{i}(H)=\chi _{i}(H). \end{aligned}$$

Now, let $\Delta (G),\Delta (H)\ge 2$. Then, G has $\Delta (G)$ vertices having a common neighbor. Thus, $\omega \big (\mathcal {N}(G)\big )\ge \Delta (G)$, in which $\omega$ denotes the clique number. This leads to

$$\begin{aligned} \chi \big (\mathcal {N}(G^{-})\boxtimes \mathcal {N}(H^{-})\big )\ge \chi \big (K_{\Delta (G)}\boxtimes \mathcal {N}(H^{-})\big )\ge \Delta (G)+\chi \big (\mathcal {N}(H^{-})\big ). \end{aligned}$$

The second inequality follows from [16] (see also [19]). Consequently, by (3) and Lemma 1, we deduce that $\chi _{i}(G\times H)\ge \chi _{i}(H)+\Delta (G)$. Analogously, we get $\chi _{i}(G\times H)\ge \chi _{i}(G)+\Delta (H)$, and therefore $\chi _{i}(G\times H)\ge \max \{\chi _{i}(G)+\Delta (H),\chi _{i}(H)+\Delta (G)\}$.

To see the sharpness of the bound, we consider the direct product $C_{2r+1}\times C_{2t+1}$ with $r,t\ge 2$. From [19], it is known that $\chi (C_{2r+1}\boxtimes C_{2t+1})=5$. Thus, we have $\chi _{i}(C_{2r+1}\times C_{2t+1})=\chi \big (\mathcal {N}(C_{2r+1}\times C_{2t+1})\big )=\chi \big (\mathcal {N}(C_{2r+1})\boxtimes \mathcal {N}(C_{2t+1})\big )=\chi (C_{2r+1}\boxtimes C_{2t+1})=5=\max \{\chi _{i}(C_{2r+1}),\chi _{i}(C_{2t+1})\}+2$, where the third equality comes from the fact that the two-step graph of an odd cycle is isomorphic to itself. $\square$

2.2 Direct Product of Two Cycles

The 2-distance chromatic number of the Cartesian product of two cycles (namely the torus graphs) has been widely investigated in several papers (for example, see [5, 25, 26]). In 2015, Chegini et al. [5] proved that $\chi _{2}(C_{m}\square C_{n})\le 6$ for all integers $m,n\ge 10$. Also, the injective chromatic number of torus graphs has recently been studied in [31].

Regarding the direct product of two cycles, Kim et al. [18] proved the following result.

Theorem 2

The following statements hold.

(i) If $m\ge 40$ and $n\ge 48$ are even, then

$$\begin{aligned} \chi _{2}(C_{m}\times C_{n})=\left\{ \begin{array}{lll} 5 &{} \quad \hbox {if }m,n\equiv 0 (\hbox {mod }5 ),\\ 6 &{} \quad \hbox {otherwise.}\\ \end{array} \right. \end{aligned}$$

(ii) If $m\ge 40$ is even and $n\ge 25$ is odd, then

$$\begin{aligned} \chi _{2}(C_{m}\times C_{n})=\left\{ \begin{array}{lll} 5 &{} \quad \hbox {if }m,n\equiv 0 (\hbox {mod }5),\\ 6 &{} \quad \hbox {otherwise.}\\ \end{array} \right. \end{aligned}$$

(iii) If $m\ge 45$ and $n\ge 53$ are odd, then

$$\begin{aligned} \chi _{2}(C_{m}\times C_{n})=\left\{ \begin{array}{lll} 5 &{} \quad \hbox {if }m,n\equiv 0 (\hbox {mod }5),\\ 6 &{} \quad \hbox {otherwise.}\\ \end{array} \right. \end{aligned}$$

In concordance with this, we see that the exact values of the 2-distance chromatic number of $C_{m}\times C_{n}$ is not yet known for a large number of values of $m,n\ge 3$. In contrast with this, in our investigation, we make a related and complete study of the injective chromatic number of these graphs.

Regarding injective coloring, the isomorphism

$$\begin{aligned} \mathcal {N}(G\times H)\cong \big (\mathcal {N}(G^{-})\boxtimes \mathcal {N}(H^{-})\big )^{-}+\overline{K_{p}}, \end{aligned}$$

with $p=|I_{\mathcal {N}(G\times H)}|$ (given in Lemma 1), provides us with a useful tool so as to obtain the exact values of $\chi _{i}(C_{m}\times C_{n})$ for all possible values of m and n. Along with the above isomorphism, we shall need the following result due to Vesztergombi [29] in 1979 (see also [19]).

Lemma 2

([19, 29]) For any $s,t\ge 2$, $\chi (C_{2s+1}\boxtimes C_{2t+1})=5$.

We are now in a position to present the main result of this section. Note that, in the following theorem, $\chi _{i}(C_{m}\times C_{n})$ for the other possible values for m and n which are not appeared here can be determined by taking into account the trivial isomorphism $C_{m}\times C_{n}\cong C_{n}\times C_{m}$ for all $m,n\ge 3$.

Theorem 3

For any integers $m,n\ge 3$,

$$\begin{aligned} \chi _{i}(C_{m}\times C_{n})=\left\{ \begin{array}{lll} 4 &{} \quad \hbox {if }m,n\equiv 0 (\hbox {mod }4),\\ 5 &{} \quad \hbox {if }``m\ne 6\hbox { is even and }n\ge 5\hbox { is odd }''\hbox { or }``\hbox { both }m,n\ge 5\hbox { are } \hbox {odd }''\\ &{} \quad \hbox {or }``(m,n)=(4s+2,4t+2)\hbox { with }s,t\ge 2''\\ &{} \quad \hbox {or }``(m,n)=(4,4t+2)\hbox { with }t\ge 2'',\\ 6 &{} \quad \hbox {if }m=4s\hbox { for }s\ge 1\hbox { and }n\in \{3,6\},\\ 7 &{} \quad \hbox {if }m\in \{3,6\}\hbox { and }n\in \{2t+1,4t+2\}\hbox { with }t\ge 3,\\ 8 &{} \quad \hbox {if }m\in \{3,6\}\hbox { and }n=5,\\ 9 &{} \quad \hbox {if }m\in \{3,6\}\hbox { and }n=3.\\ \end{array} \right. \end{aligned}$$

Proof

We distinguish three cases depending on the parity of m and n by taking into account the fact that both direct and strong products are commutative.

Case 1. Both m and n are odd. Let $m=2s+1$ and $n=2t+1$ for some $s,t\ge 1$. It can be easily observed that if G is a cycle of order $n\ge 3$, then $\mathcal {N}(G)$ is also a cycle of order n when n is odd. Suppose first that $s,t\ge 2$. We then deduce from (1), Lemmas 1 and 2 that

$$\begin{aligned} \chi _{i}(C_{2s+1}\times C_{2t+1})=\chi (C_{2s+1}\boxtimes C_{2t+1})=5. \end{aligned}$$

We now assume by symmetry that one of the factors, say $C_{2s+1}$, is of order three. From [19], we know that $\chi (K_{m}\boxtimes C_{2n+1})=2m+\lceil m/n\rceil$ for $m\ge 1$ and $n\ge 2$. This shows that $\chi _{i}(C_{3}\times C_{5})=8$ and that $\chi _{i}(C_{3}\times C_{2t+1})=7$ for $t\ge 3$. On the other hand, it is readily seen that $\chi _{i}(C_{3}\times C_{3})=9$.

Case 2. Suppose that m is even and $n=2t+1$ for some $t\ge 1$. Suppose first that $m=4k+2$ for some $k\ge 1$. Notice that if G is a cycle of order p, then $\mathcal {N}(G)$ is the disjoint union of two cycles of order p/2 when $p\ge 6$ is even, and it is $K_{2}+K_{2}$ if $p=4$. With this in mind, we conclude that

$$\begin{aligned} \chi _{i}(C_{m}\times C_{2t+1})=\chi \big ((C_{2k+1}+C_{2k+1})\boxtimes C_{2t+1}\big )=\chi (C_{2k+1}\boxtimes C_{2t+1}). \end{aligned}$$

Therefore, $\chi _{i}(C_{4k+2}\times C_{2t+1})=5$ for all $k,t\ge 2$ (by using Lemma 2). So, we need to discuss the cases when $k=1$ and when $t=1$ separately. In particular, we have $\chi _{i}(C_{6}\times C_{5})=8$ and $\chi _{i}(C_{6}\times C_{2t+1})=7$ for $t\ge 3$. Moreover, it is easy to see that $\chi _{i}(C_{6}\times C_{3})=\chi (C_{3}\boxtimes C_{3})=9$. Also, the possible values for $\chi _{i}(C_{4k+2}\times C_{3})=\chi (C_{2k+1}\boxtimes C_{3})$ has just been discussed.

We now assume that $m=4k$ for an integer $k\ge 1$. In what follows, we take advantage of the following useful claim.

Claim 1. Let $k\ge 2$ be an integer. For any odd integer $n\ge 3$,

$$\begin{aligned}\chi (C_{2k}\boxtimes C_{n})=\left\{ \begin{array}{lll} 5 &{} \quad \hbox {if }n\ge 5,\\ 6 &{} \quad \hbox {if }n=3. \end{array} \right. \end{aligned}$$

Proof of Claim 1. We observe that $\omega (C_{3}\boxtimes C_{2k})=6$, in which $\omega$ denotes the clique number. Therefore, the pattern given in Fig. 1 represents an optimal 6-coloring of $C_{3}\boxtimes C_{2k}\cong C_{2k}\boxtimes C_{3}$ for each $k\ge 2$ (note that by an optimal k-coloring of a graph G we mean a proper coloring of G with $k=\chi (G)$ colors). So, from now on, we assume that $n\ge 5$ (odd).

Fig. 1

An optimal 6-coloring of $C_{3}\boxtimes C_{2k}$ for each $k\ge 2$

It is shown in [28] that $\alpha (C_{2i}\boxtimes C_{2j+1})=ij$, for all positive integers $i\ge 2$ and j, in which $\alpha$ stands for the independence number. Therefore,

$$\begin{aligned} \chi (C_{2k}\boxtimes C_{2t+1})\ge \lceil (2k)(2t+1)/kt\rceil =5. \end{aligned}$$

(5)

On the other hand, the pattern in Fig. 2 gives us a 5-coloring of $C_{2k}\boxtimes C_{2t+1}$ for all integers $k,t\ge 2$. This fact together with the inequality (5) leads to $\chi (C_{2k}\boxtimes C_{n})=5$ for each $k\ge 2$ and odd integer $n\ge 5$. $(\square )$

Fig. 2

An optimal 5-coloring of $C_{2k}\boxtimes C_{2t+1}$ for all integers $k,t\ge 2$

We now infer from Claim 1 that $\chi _{i}(C_{4k}\times C_{n})=\chi (C_{2k}\boxtimes C_{n})=5$ for each $k\ge 2$ and odd integer $n\ge 5$, and that $\chi _{i}(C_{4k}\times C_{3})=6$ for each $k\ge 2$. Furthermore, in the case when $k=1$, we have $\chi _{i}(C_{4}\times C_{2t+1})=\chi (K_{2}\boxtimes C_{2t+1})$. Therefore, $\chi _{i}(C_{4}\times C_{2t+1})=5$ for $t\ge 2$. Moreover, it is easy to see that $\chi _{i}(C_{4}\times C_{3})=\chi (K_{2}\boxtimes C_{3})=6$.

Case 3. Both m and n are even. If $m=4s+2$ and $n=4t+2$ for some $s,t\ge 1$, then $\chi _{i}(C_{4\,s+2}\times C_{4t+2})=\chi (C_{2\,s+1}\boxtimes C_{2t+1})$. Therefore, $\chi _{i}(C_{4\,s+2}\times C_{4t+2})=5$ if $s,t\ge 2$ as we discussed in Case 1. On the other hand, for the remaining possible values of s and t, it suffices to consider the case when $s=1$. In such a situation, we have $\chi _{i}(C_{6}\times C_{4t+2})=\chi (C_{3}\boxtimes C_{2t+1})$. Hence, $\chi _{i}(C_{6}\times C_{4t+2})=7$ for $t\ge 3$. Moreover, it is easy to see that $\chi _{i}(C_{6}\times C_{6})=\chi (C_{3}\boxtimes C_{3})=9$ and $\chi _{i}(C_{6}\times C_{10})=\chi (C_{3}\boxtimes C_{5})=8$.

If $m=4\,s$ and $n=4t+2$ for some $s,t\ge 1$, then $\chi _{i}(C_{4s}\times C_{4t+2})=\chi (C_{2s}\boxtimes C_{2t+1})$ for $s\ge 2$ and $t\ge 1$. In such a situation, Claim 1 implies that $\chi _{i}(C_{4\,s}\times C_{6})=6$ for $s\ge 2$, and $\chi _{i}(C_{4s}\times C_{4t+2})=5$ for $s,t\ge 2$. We also have $\chi _{i}(C_{4}\times C_{6})=6$ and $\chi _{i}(C_{4}\times C_{4t+2})=\chi (K_{2}\boxtimes C_{2t+1})=5$ for $t\ge 2$.

Fig. 3

An optimal 4-coloring of $C_{2s}\boxtimes C_{2t}$ for each $s,t\ge 1$. Here, we let $C_{2}=K_{2}$ for the sake of convenience

Finally, let $m=4\,s$ and $n=4t$ for some $s,t\ge 1$. It is clear that the $(2s\times 2t)$-pattern depicted in Fig. 3 gives us a 4-coloring of $C_{2s}\boxtimes C_{2t}$ for each $s,t\ge 1$. We here assume $C_{2}=K_{2}$ for the sake of convenience. On the other hand, we get $\chi _{i}(C_{4\,s}\times C_{4t})=\chi (C_{2\,s}\boxtimes C_{2t})=4$ since $\omega (C_{2s}\boxtimes C_{2t})=4$. This completes the proof. $\square$

3 Lexicographic and Corona Product Graphs

Our first aim in this section is to give sharp lower and upper bounds on $\chi _{i}(G\circ H)$. We also prove that $\chi _{2}$ and $\chi _{i}$ are the same in the case of lexicographic product graphs when both G and H have no isolated vertices.

Theorem 4

Let G be a connected graph of order at least two and let H be any graph with $i_{H}$ isolated vertices. Then,

$$\begin{aligned} \chi _{i}(G\circ H)\le \chi _{2}(G)|V(H)|-i_{H}\big (\chi _{2}(G)-\chi _{i}(G)\big ). \end{aligned}$$

Moreover, if H has no isolated vertices, then

$$\begin{aligned} \chi _{i}(G\circ H)=\chi _{2}(G\circ H)\ge (\Delta (G)+1)|V(H)|. \end{aligned}$$

Proof

Let ${\mathbb {A}}=\{A_{1},\dots ,A_{\chi _{i}(G)}\}$ and ${\mathbb {B}}=\{B_{1},\dots ,B_{\chi _{2}(G)}\}$ be a $\chi _{i}(G)$-coloring and a $\chi _{2}(G)$-coloring, respectively. Also, let $I_{H}$ be the set of isolated vertices of H. We set

$$\begin{aligned} {\mathbb {P}}=\{A_{i}\times \{h\}\mid 1\le i\le \chi _{i}(G), h\in I_{H}\}\cup \{B_{i}\times \{h\}\mid 1\le i\le \chi _{2}(G), h\in V(H)\setminus I_{H}\}. \end{aligned}$$

Clearly, ${\mathbb {P}}$ is a vertex partition of $G\circ H$.

Suppose that there exists a vertex $(g,h')$ adjacent to two distinct vertices $(g',h),(g'',h)\in A_{i}\times \{h\}$, for some $1\le i\le \chi _{i}(G)$ and $h\in I_{H}$. Note first that g cannot simultaneously be adjacent to both $g'$ and $g''$, due to the fact that $A_{i}$ is an open packing in G. So, it must happen, without loss of generality, that $g=g''$. However, this means that $hh'$ is an edge of H, which is a contradiction to the fact that h is an isolated vertex of H. Therefore, $A_{i}\times \{h\}$ is an open packing in $G\circ H$.

If $(g,h')$ is adjacent to two distinct vertices $(g',h),(g'',h)\in B_{i}\times \{h\}$ for some $1\le i\le \chi _{2}(G)$ and $h\in V(H){\setminus } I_{H}$, then $g',g''\in N_{G}[g]\cap B_{i}$. This is a contradiction since any two vertices of $B_{i}$ are at distance larger than two in G. This shows that $B_{i}\times \{h\}$ is a open packing in $G\circ H$. So, we have concluded that ${\mathbb {P}}$ is an injective coloring of $G\circ H$. Therefore,

$$\begin{aligned} \chi _{i}(G\circ H) \le |{\mathbb {P}}|{} & {} =\chi _{i}(G)i_{H}+\chi _{2}(G)\big (|V(H)|-i_{H}\big )\nonumber \\{} & {} =\chi _{2}(G)|V(H)|-i_{H}\big (\chi _{2}(G)-\chi _{i}(G)\big ). \end{aligned}$$

(6)

The bound is sharp for a large number of infinite families of graphs. For instance, consider the lexicographic product graph $F=P_{r}\circ (P_{s}+\overline{P_{t}})$ with $r\ge 3$, $s\ge 2$ and $t\ge 1$. Let $V(P_r)=\{u_{1},\dots ,u_{r}\}$, $V(P_s)=\{v_{1},\dots ,v_{s}\}$ and $V(\overline{P_t})=\{w_{1},\dots ,w_{t}\}$. Set $F'=F[\{u_{1},u_{2},u_{3}\}\times \big (V(P_{s})\cup V(\overline{P_{t}})\big )]$. Let $f':V(F')\rightarrow \{1,2,\dots ,\chi _{i}(F')\}$ be any $\chi _{i}(F')$-coloring. Note that in the subgraph of $F'$ induced by $\{u_{1},u_{2},u_{3}\}\times V(P_{s})$, each edge lies on a triangle. Therefore, no two vertices of this induced subgraph receive the same color by $f'$. This shows that $f'$ assigns 3s colors to the vertices of $\{u_{1},u_{2},u_{3}\}\times V(P_{s})$. On the other hand, because $(u_{2},v_{1})$ is adjacent to all vertices in $\{u_{1},u_{3}\}\times \big (V(P_{s})\cup V(P_{t})\big )$, it follows that every vertex in this set receives a unique color by $f'$. In fact, we observe that $f'$ assigns 2t colors to the vertices in $Q=\{u_{1},u_{3}\}\times V(P_{t})$ and that $f'\big (\{u_{1},u_{2},u_{3}\}\times V(P_{s})\big )\cap f'(Q)=\emptyset$. The above discussion shows that

$$\begin{aligned} \begin{array}{lcl} \chi _{i}(F)\ge \chi _{i}(F')&{}=&{}|f'\big (\{u_{1},u_{2},u_{3}\}\times V(P_{s})\big )| +\sum _{i=1}^{t}|f'(\{u_{1},u_{2},u_{3}\}\times \{w_{i}\})|\\ &{}\ge &{}3s+2t\\ &{}=&{}\chi _{2}(P_{r})|V(P_{s}+\overline{P_{t}})|-i_{P_{s}+\overline{P_{t}}}(\chi _{2}(P_{r})-\chi _{i}(P_{r})). \end{array} \end{aligned}$$

This results in the equality in the upper bound.

Suppose now that H has no isolated vertices. Let $(g,h)(g',h')\in E(G\circ H)$. If $g=g'$, then $(g'',h)$ is adjacent to both (g, h) and $(g',h')$ in which $g''$ is any vertex of G adjacent to g. Suppose that $gg'\in E(G)$. There exists $h''\in V(H)$ adjacent to h because H does not have isolated vertices. So, $(g,h'')$ is adjacent to both (g, h) and $(g',h')$ by the adjacency rule of the lexicographic product graphs. In fact, every edge of $G\circ H$ lies on a triangle. This shows that every open packing in $G\circ H$ is an independent set. In particular, a subset of $V(G\circ H)$ is a packing if and only if it is an open packing. Therefore, $\chi _{i}(G\circ H)=\chi _{2}(G\circ H)$.

Let g be a vertex of G of maximum degree. It happens that $\textrm{diam}\big ((G\circ H)[N_{G}[g]\times V(H)]\big )\le 2$. This in particular implies that any 2-distance coloring of $G\circ H$ assigns at least $|N_{G}[g]\times V(H)|=(\Delta (G)+1)|V(H)|$ colors to the vertices of $G\circ H$. Consequently, $\chi _{i}(G\circ H)=\chi _{2}(G\circ H)\ge (\Delta (G)+1)|V(H)|$.

That the lower bound is sharp, may be seen as follows. It is known that $\chi _{2}(T)=\Delta (T)+1$ for any tree T (see Theorem 2.4 in [23] for $k=2$). Let T be a nontrivial tree and let H be any graph with no isolated vertices. Then, $\chi _{i}(T\circ H)=\chi _{2}(T\circ H)=(\Delta (T)+1)|V(H)|$ by considering both lower and upper bounds. This completes the proof. $\square$

Ghazi et al. [9] exhibited the exact formula $\chi _{2}(G\circ H)=\chi _{2}(G)|V(H)|$ for all connected graphs G and H. In what follows, we show that this equality is not true as it stands. In Fig. 4, we consider the graph $C_{7}\circ C_{5}$ without drawing the edges (for the sake of convenience). Note that the assigned numbers to the vertices represent a 2DC of $C_{7}\circ C_{5}$ with 18 colors. So, $\chi _{2}(C_{7}\circ C_{5})\le 18<20=\chi _{2}(C_{7})|V(C_{5})|$.

Fig. 4

A counterexample to the formula $\chi _{2}(G\circ H)=\chi _{2}(G)|V(H)|$ for all connected graphs G and H

We next present a closed formula for $\chi _{i}(G\odot H)$.

Theorem 5

For any graphs G and H with no isolated vertices,

$$\begin{aligned} \chi _{i}(G\odot H)\in \big \{\chi _{i}(G),|V(H)|+\Delta (G),|V(H)|+\Delta (G)+1\big \}. \end{aligned}$$

Proof

Clearly, any $\chi _{i}(G\odot H)$-coloring assigns at least $\chi _{i}(G)$ colors to the vertices of G since G is a subgraph of $G\odot H$. So, $\chi _{i}(G\odot H)\ge \chi _{i}(G)$.

For each $1\le i\le |V(G)|$, assume that $V(H_{i})=\{u_{i1},\dots ,u_{i|V(H)|}\}$. Let ${\mathbb {A}}=\{A_{1},\dots ,A_{\chi _{i}(G)}\}$ be a $\chi _{i}(G)$-coloring. In what follows, we construct a mapping f on $V(G\odot H)$ that assigns the colors $1,\dots ,\chi _{i}(G)$ to the vertices in $A_{1},\dots ,A_{\chi _{i}(G)}$, respectively. In particular, f turns out to be a $\chi _{i}(G)$-coloring. We consider two cases depending on $\chi _{i}(G)$.

Case 1. $|V(H)|\le \chi _{i}(G)-\Delta (G)-1$. We choose an arbitrary vertex $v_{i}$ and let it be in $A_k$. We now extend f by assigning |V(H)| colors $r_1,\dots ,r_{|V(H)|}\in \{1,\dots ,\chi _{i}(G)\}$ to the vertices $u_{i1},\dots ,u_{i|V(H)|}$ such that $N_{G}[v_{i}]\cap A_{r_j}=\emptyset$ for every $1\le j\le |V(H)|$ (there do exist such colors since $|V(H)|\le \chi _{i}(G)-\deg _{G}(v_i)-1$). By iterating this process for all vertices in V(G), we note that f is an injective coloring of $G\odot H$ assigning $\chi _{i}(G)$ colors to the vertices of $G\odot H$. Therefore, $\chi _{i}(G\odot H)\le \chi _{i}(G)$, and hence $\chi _{i}(G\odot H)=\chi _{i}(G)$.

Case 2. $|V(H)|\ge \chi _{i}(G)-\Delta (G)$. We need to distinguish two more possibilities depending also on the behavior of vertices of maximum degree in G.

Subcase 2.1. Suppose that we have “$|V(H)|=\chi _{i}(G)-\Delta (G)$” and the property that “every vertex $v_j$ of maximum degree in G has a (unique) neighbor in the open packing (color class) from ${\mathbb {A}}$ containing $v_j$.” In such a situation, similarly to the argument given in Case 1, $G\odot H$ can be injectively colored with $\chi _{i}(G)$ colors. Thus, $\chi _{i}(G\odot H)=\chi _{i}(G)$.

Subcase 2.2. Suppose that “$|V(H)|>\chi _{i}(G)-\Delta (G)$” or we have “$|V(H)|=\chi _{i}(G)-\Delta (G)$ with the property that there exists a vertex $v_j$ of maximum degree in G having no neighbor in the open packing (color class) from ${\mathbb {A}}$ containing $v_j$.” Moreover, we consider the following facts:

$\bullet$ no vertex of $H_j$ receives the color $f(v_j)$, otherwise there would be a vertex of $H_j$ adjacent to at least two vertices with the same color $f(v_j)$ since H has no isolated vertices; and

$\bullet$ none of the colors, assigned to the vertices of those open packing sets (color classes) from ${\mathbb {A}}$ containing the neighbors of $v_j$, can be assigned to the vertices of $H_j$.

The above argument shows that $G\odot H$ cannot be injectively colored with $\chi _{i}(G)$ colors. Hence, $\chi _{i}(G\odot H)>\chi _{i}(G)$.

Obviously, f assigns at most $\Delta (G)+1$ colors to the vertices in $N_{G}[v_i]$ for each $1\le i\le n$. We now choose a vertex $v_{i}\in A_{k}$. If $|V(H)|\le \chi _{i}(G)-\deg _{G}(v_i)-1$, then we assign |V(H)| colors $r_1,\dots ,r_{|V(H)|}\in \{1,\dots ,\chi _{i}(G)\}$ to the vertices $u_{i1},\dots ,u_{i|V(H)|}$ such that $N_{G}[v_{i}]\cap A_{r_j}=\emptyset$, with $1\le j\le |V(H)|$, similarly to Case 1 (indeed, f assigns at most $\chi _{i}(G)$ colors among $\{1,\cdots ,\chi _{i}(G)\}$ to the vertices in $V(H_i)\cup V(G)$). Otherwise, we deal with the following two possibilities.

Subcase 2.2.1. $\chi _{i}(G)\in \{\deg _{G}(v_i),\deg _{G}(v_i)+1\}$. In such a situation, we assign |V(H)| new colors $1',\cdots ,|V(H)|'$ to the vertices $u_{i1},\dots ,u_{i|V(H)|}$, respectively. In fact, f has used $|V(H)|+\Delta (G)$ or $|V(H)|+\Delta (G)+1$ colors in order to injectively color the vertices in $V(H_i)\cup V(G)$.

Subcase 2.2.2. $\chi _{i}(G)>\deg _{G}(v_i)+1$. We then assign $k(i)=\chi _{i}(G)-\deg _{G}(v_i)-1$ colors $r_1,\dots ,r_{k(i)}\in \{1,\dots ,\chi _{i}(G)\}$ to the vertices $u_{i1},\dots ,u_{ik(i)}$ such that $N_{G}[v_{i}]\cap A_{r_j}=\emptyset$ with $1\le j\le k(i)$, and $t(i)=|V(H)|-k(i)$ new colors $1',\cdots ,t(i)'$ to the vertices $u_{i(k(i)+1)},\dots ,u_{i|V(H)|}$, respectively.

Iterating this process for all vertices $v_i$ with $\chi _{i}(G)>\deg _{G}(v_i)+1$, we observe that f assigns at most

$$\begin{aligned} \chi _{i}(G)+\max _{i}\{t(i)\}=\chi _{i}(G)+|V(H)|-\chi _{i}(G)+\Delta (G)+1=|V(H)|+\Delta (G)+1 \end{aligned}$$

colors in order to injectively color the vertices in $V(H_i)\cup V(G)$.

Notice that the extension of f given in Subcases 2.2.1 and 2.2.2 results in an injective coloring of $G\odot H$. From this fact, we deduce that $\chi _{i}(G\odot H)\le |V(H)|+\Delta (G)+1$. On the other hand, $\chi _{i}(G\odot H)\ge \Delta (G\odot H)=|V(H)|+\Delta (G)$ by the inequality (4). Therefore, $\chi _{i}(G\odot H)$ equals either $|V(H)|+\Delta (G)$ or $|V(H)|+\Delta (G)+1$.

Altogether, the arguments above show that $\chi _{i}(G\odot H)\in \big \{\chi _{i}(G),|V(H)|+\Delta (G),|V(H)|+\Delta (G)+1\big \}$. $\square$

We conclude this section with remarking that $\chi _{i}(G\odot H)$ assumes all three values given in Theorem 5 depending on our choices for G and H. To see this, let $G=K_{r}\square K_{s}$ for two integers $r,s\ge 3$. It is clear that any injective coloring f of $G\odot K_{2}$ assigns rs colors, say $1,2,\dots ,rs$, to the vertices in V(G). Moreover, by assigning two colors from $\{1,2,\dots ,rs\}\setminus \{f(u)\mid u\in N_{G}[v]\}$ to the vertices in $N_{G\odot K_{2}}[v]{\setminus } N_{G}[v]$ for each $v\in V(G)$, we get an injective coloring of $G\odot K_{2}$ with rs colors. Therefore, $\chi _{i}(G\odot K_{2})=rs=\chi _{i}(G)$.

Brešar et al. [3] showed that $\chi _{i}(T)=\Delta (T)$ for any tree T on at least two vertices. With this in mind, taking H to be any graph with no isolated vertices, we observe that $T\odot H$ satisfies the assumption given in Subcase 2.2 in the proof of Theorem 5. Hence, $\chi _{i}(T\odot H)\in \{|V(H)|+\Delta (T),|V(H)|+\Delta (T)+1\}$. On the other hand, any injective coloring of T with $\Delta (T)$ colors can be extended to an injective coloring of $T\odot H$ with $|V(H)|+\Delta (T)$ colors by assigning |V(H)| new colors to the vertices of $H_{1},\dots ,H_{|V(T)|}$. This leads to $\chi _{i}(T\odot H)=|V(H)|+\Delta (T)$.

Finally, we observe that for any graph H with no isolated vertices, $\chi _{i}(K_{n}\odot H)=n+|V(H)|=|V(H)|+\Delta (K_{n})+1$ for $n\ge 3$.