Interval edge colorings of the generalized lexicographic product of some graphs

1.   Introduction

All graphs considered in this paper are finite, undirected, and simple graphs. Let $V(G)$ and $E(G)$ denote the sets of vertices and edges of graph $G$, respectively. The degree of a vertex $v$ in $G$ is denoted by $d_G(v)$, the maximum degree of $G$ by $\Delta(G)$, and the complement of the graph $G$ by $\overline G$. We denote by $[a, b]$ the interval of integers $\{a, \ldots, b\}$, and by $(x)_k$ the $x\pmod k$, where $x$ is an integer and $k$ is a positive integer. The terms and concepts that we do not define can be found in ^[3].

The notion of interval colorings was introduced in 1987 by Asratian and Kamalian ^[1]. This concept was introduced for studying the problems that are related to constructing timetables without "gaps" for teachers and classes. Hansen ^[6] presented a similar scenario: a school can schedule parent-teacher conferences in consecutive time slots if the bipartite graph, with parents and teachers as vertices and meetings as edges, has an interval coloring.

A proper edge coloring of a graph $G$ is a coloring of the edges of $G$ such that no two adjacent edges receive the same color. The chromatic index $\chi'(G)$ of a graph G is the minimum number of colors used in a proper edge coloring of $G$. If $\alpha$ is a proper edge coloring of $G$ and $v \in V(G)$, we denote by $S(v, \alpha)$ the set of colors of edges incident to $v$.

A proper edge coloring of a graph $G$ with colors $1, \ldots, t$ is an interval $t$-coloring if all colors are used, and for any vertex $v$ of $G$, the set $S(v, \alpha)$ is an interval of consecutive integers. A graph $G$ is interval colorable if it has an interval $t$-coloring for some positive integer $t$. The set of interval colorable graphs is denoted by $\mathfrak{N}$. For a graph $G\in\mathfrak{N}$, the least and the greatest values of $t$ for which $G$ has an interval $t$-coloring are denoted by $w(G)$ and $W(G)$, respectively.

The Vizing Theorem^[19] states that $\chi'(G) = \Delta(G)$ or $\chi'(G) = \Delta(G)+1$. Graphs with $\chi'(G) = \Delta(G)$ are said to be Class 1; graphs with $\chi'(G) = \Delta(G)+1$ are said to be Class 2. Asratian and Kamalian ^[1] proved that if $G\in\mathfrak{N}$, then $\chi'(G) = \Delta(G)$, that is, $G$ is said to be Class 1. Not all Class 1 graphs are interval colorable; even a simple graph such as wheel $W_n(n\geq3)$ is not necessarily interval edge colorable. Giaro et al.^[4] proved that $W_n\in\mathfrak{N}$ if and only if $n = 4, 7, 10$; otherwise, $W_n\notin\mathfrak{N}$. Asratian et al.^[2], Holyer ^[7], and Sevastjanov ^[16] proved that it is a NP-complete problem to decide whether a regular graph or a bipartite graph has an interval coloring or not. For a graph $G\in \mathfrak{N}$, the exact values of the parameters $W(G)$ and $w(G)$ are known only for paths, even cycles, trees, complete bipartite graphs ^[1,9], and Möbius ladders ^[12]. However, for some common interval-colorable graphs, such as complete graphs and $n$-dimensional cubes ^[13], the exact upper and lower bounds on the number of colors remain unknown.

We know that the generalized lexicographic product of graphs is one of the important tools for constructing classes of graphs in graph theory. Common graph operations, such as the join of graphs and the lexicographic product of graphs, are essentially special cases of the generalized lexicographic product. However, to the best knowledge of the author, there are no studies related to the interval edge coloring of generalized lexicographic products. This fact motivates us to begin an exploration of the interval edge coloring of the generalized lexicographic product of graphs.

The generalized lexicographic product of graphs is defined as follows ^[17]: let $G$ be a graph with vertex set $V(G) = \{u_1, \ldots, u_{m}\}$, $m\geq2$, and let $h_m = (H_i)_{i\in\{1, \ldots, m\}}$ be a sequence of vertex-disjoint with $V(H_i) = \{x_1^{(i)}, \ldots, x_{n_i}^{(i)}\}$, $n_i\geq 1$. The generalized lexicographic products $G[h_m]$ of $G$ and $h_m$ is a simple graph with vertex set $\cup_{i = 1}^{m}V(H_i)$, in which $x_p^{(i)}$ is adjacent to $x_q^{(j)}$ if and only if either $u_i = u_j$ and $x_p^{(i)}x_q^{(i)}\in E(H_i)$ or $u_iu_j\in E(G)$. If $H_i\cong H$ for every $i\in\{1, \ldots, m\}$, then $G[h_m]$ becomes the lexicographic product of $G$ and $H$, denoted by $G[H]$. If $G\cong K_2$, then $G[h_2]$ denotes a join $H_1+H_2$ of vertex disjoint graphs $H_1$ and $H_2$. If $G\cong K_m$, and every graph $H_i$ is the complement of a complete graph with $n_i$ vertices (that is, $H_i\cong \overline{k_{n_i}}$), then $G[h_m]$ denotes a complete $m$-partite graph $K_{n_{1}, \ldots, n_m}$. For convenience, we write $\widetilde{G}$ to denote $G[h_m]$.

Let $G^{(1)} = G[\overline{K_n}]$ and $G^{(2)} = \bigcup_{i = 1}^{m}H_i$, then $\widetilde{G}$ can be decomposed into the union of two edge-disjoint subgraphs $G^{(1)}$ and $G^{(2)}$, that is,

Figure 1 shows the decomposition of $\widetilde{G} = W_7[h_7]$, where $h_7 = (H_i)_{i\in\{1, \ldots, 7\}}$ is a sequence of vertex-disjoint graphs, each with $n$ vertices.

Kamalian ^[10] proved that the complete bipartite graph $K_{m, n}$ has an interval $t$-coloring if and only if $m+n-\gcd(m, n)\leq t\leq m+n-1$. Grzesik and Khachatrian ^[5] proved that complete tripartite graphs $K_{1, m, n}$ are interval colorable if and only if $\gcd(m+1, n+1) = 1$. Puning Jing et al.^[8] extended the result and obtained several sufficient conditions for a complete tripartite graph $K_{l, m, n}$ to admit an interval coloring, where $\gcd(m, n)$ is the greatest common divisor of $m$ and $n$. Petrosyan ^[14] investigated interval edge colorings of lexicographic products and obtained the following two results.

Theorem 1.1. If $G\in\mathfrak{N}$, then $G[\overline{k_n}]\in\mathfrak{N}$, and $w(G[\overline{k_n}])\leq w(G)n$, $W(G[\overline{k_n}])\geq (W(G)+1)n-1$.

Theorem 1.2. If $G, H\in\mathfrak{N}$ and $H$ is a $r$-regular graph, then $G[H]\in\mathfrak{N}$, and $w(G[H])\leq w(G)|V(H)|+r$, $W(G[H])\geq W(G)|V(H)|+r$.

Yepremyan et al. ^[15] proved that if $G$ is a tree and $H$ is a path or a star, then $G[H]\in \mathfrak{N}$. Tepanyan et al. ^[18] proved that if $G\in\mathfrak{N}$, and $H$ is a regular graph, complete bipartite graph, or tree, then $G[H]\in\mathfrak{N}$. They obtained the following results:

Theorem 1.3. For all positive integers $n\geq2$, if $G\in\mathfrak{N}$, then $G[C_{2n}]\in\mathfrak{N}$, and $w(G[C_{2n}])\leq2(w(G)n+1)$, $W(G[C_{2n}])\geq(2W(G)+1)n+1$.

In this paper, our goal is to find sufficient conditions for a generalized lexicographic product $\widetilde{G}$ to admit an interval coloring. Moreover, we also hope to present some sharp bounds on $w(\widetilde{G})$ and $W(\widetilde{G})$, where $G$ is an interval colorable graph with $m$ vertices and all graphs in $h_m$ have $n$ vertices, $n\geq4$.

The following two lemmas will be used later:

Lemma 1.1. ^[11] If $\alpha$ is an edge-coloring of a connected graph $G$ with colors $1, \ldots, t$ such that the edges incident to each vertex $v\in V(G)$ are colored by distinct and consecutive colors and $\min\{\alpha(u_iu_j)|u_iu_j\in E(G) \} = 1$, $\max\{\alpha(u_iu_j)|u_iu_j\in E(G) \} = t$, then $\alpha$ is an interval $t$-coloring of $G$.

Lemma 1.2. Let $\alpha$ be an interval $t$-coloring of $G$, and let $\beta(u_iu_j) = t-\alpha(u_iu_j)+1$ for every edge $u_iu_j\in E(G)$, then $\beta$ is also an interval $t$-coloring of $G$.

Proof. For any vertex $u_i\in V(G)$, we assume that $S(u_i, \alpha) = [a, a+d(u_i)-1]$. By the definition of $\beta$, we have $S(u_i, \beta) = [t-a-d(u_i)+2, t-a+1]$, that is, $\beta$ is an interval $t$-coloring of $G$. □

In Section 2, we obtained several sufficient conditions for $G[h_m]$ to admit an interval edge coloring, and we shall present the bounds of $w(\widetilde{G})$ and $W(\widetilde{G})$.

2.   Main results

Let $G\in\mathfrak{N}$. If there exists a graph $H_i$ in $h_m$ that is not isomorphic to an empty graph, then let $w(H_{k_0}) = \max\{w(H_r)|H_r\in \mathfrak{N}, r = 1, \ldots, m\}$. If $H_i$ is isomorphic to a path, then let $H_i = x_1^{(i)}\ldots x_n^{(i)}$; if $H_i$ is isomorphic to a cycle, then let $H_i = x_1^{(i)}\ldots x_n^{(i)}x_1^{(i)}$.

We define the following three classes of graphs:

(i) $\mathcal{G}_1$: each graph $H_i$ in $h_m$ is isomorphic to a path or an empty graph;

(ii) $\mathcal{G}_2$: each graph $H_i$ in $h_m$ is isomorphic to an empty graph or an interval-colorable regular graph, but not all graphs in $h_m$ are empty graphs;

(iii) $\mathcal{G}_3$: each graph $H_i$ in $h_m$ is isomorphic to a path or a cycle or an empty graph of even order, and $H_{k_0}$ is a cycle.

Let $\mathcal{G} = \mathcal{G}_1\cup \mathcal{G}_2\cup \mathcal{G}_3$. And let $\widetilde{G}\in \mathcal{G}_z$, where $z = 1, 2, 3$. If there exists an interval $t$-coloring $\alpha$ satisfying the condition I, then we say that $\widetilde{G}$ belongs to the subclass $\mathcal{G}_z^1$ of $\mathcal{G}_z$, otherwise, we say that $\widetilde{G}$ belongs to the subclass $\mathcal{G}_z^2$ of $\mathcal{G}_z$. Clearly, we have

Condition I. There exists an edge $u_{i_0}u_{j_0}\in E(G)$ with $\alpha(u_{i_0}u_{j_0}) = 1$ or $\alpha(u_{i_0}u_{j_0}) = t$, such that $H_{i_0}\cong H_{k_0}$ or $H_{j_0}\cong H_{k_0}$.

Since $G\in \mathfrak{N}$, there exists an interval $w(G)$-coloring $\alpha_1$ and an interval $W(G)$-coloring $\alpha_2$ of $G$. For any vertex $u_i\in V(G)$, denote by $\tau_i(\alpha_l)$ the $\min S(u_i, \alpha_l)$, and by $\tau_i'(\alpha_l)$ the $\max S(u_i, \alpha_l)$, where $l = 1, 2$, $i = 1, \ldots, m$.

We extend Theorem 1.1 from the lexicographic product of graphs to the generalized lexicographic product of graphs and obtain the following result:

Theorem 2.1. If $\widetilde{G}\in\mathcal{G}_1$, then $\widetilde{G}\in\mathfrak{N}$. Moreover,

where, $\lambda = 1$ if $\widetilde{G}\in\mathcal{G}_1^1$, $\lambda = 2$ if $\widetilde{G}\in\mathcal{G}_1^2$.

Proof. If $H_i$ is isomorphic to a path, then let $H_i = x_1^{(i)}\ldots x_n^{(i)}$. For the proof, we consider the following two cases:

Case 1. $\widetilde{G}\in\mathcal{G}_1^1$.

Then Condition I holds and $\lambda = 1$. By Lemma 1.2, we can assume that $\alpha(u_{i_0}u_{j_0}) = 1$. Obviously, $H_{k_0}\cong P_n$, $w(G)n+2(\lambda)_2+(\lambda+1)_2(n)_2 = w(G)n+2, (W(G)+1)n-\lambda = (W(G)+1)n-1$.

Now, we prove that $w(\widetilde{G})\leq w(G)n+2$. For this, we define an edge-coloring $\beta_1$ of the graph $\widetilde{G}$ in the following two steps:

Step 1. For every edge $x_{p}^{(i)}x_q^{(j)}\in E(G^{(1)})$, $1\leq p, q\leq n$, if $(n)_2 = 1$, then let

Otherwise, let

Step 2. For every edge $x_{p}^{(i)} x_ {p+1}^{(i)} \in E(G^{(2)})$, $1\leq p\leq n-1$, let

Let us prove that $\beta_1$ is an interval edge coloring of the graph $\widetilde{G}$.

First, we prove that the set $S(x_p^{(i)}, \beta_1)$ is an interval for each vertex $x_p^{(i)}\in V(\widetilde{G})$, where $1\leq i\leq m$, $1\leq p\leq n$.

If $(n)_2 = 1$ and $H_i$ is isomorphic to a path, by the definition of $\beta_1$, we have

If $(n)_2 = 1$ and $H_i\cong \overline{K_n}$, by the definition of $\beta_1$, we have

If $(n)_2 = 0$ and $H_i$ is isomorphic to a path, by the definition of $\beta_1$, we have

If $(n)_2 = 0$ and $H_i\cong \overline{K_n}$, by the definition of $\beta_1$, we have

Second, note that

Clearly, we have

This implies that $\beta_1$ is a proper edge coloring of $\widetilde{G}$.

Finally, we show that in the coloring $\beta_1$, all colors are used. Clearly, there exists an edge $x_{p_0}^{(i_0)}x_{p_0+1}^{(i_0)}\in E(\widetilde{G})$ such that $\beta_1(x_{p_0}^{(i_0)}x_{p_0+1}^{(i_0)}) = 1$, since in the coloring $\alpha_1$ there exists a vertex $u_{i_0}$ such that $\tau_{i_0}(\alpha_1) = 1$, and since $\beta_1(x_{1}^{(i_0)}x_{2}^{(i_0)}) = (\tau_{i_0}(\alpha_1)-1)n+1$ when $(n)_2 = 1$ and $\beta_1(x_{2}^{(i_0)}x_{3}^{(i_0)}) = (\tau_{i_0}(\alpha_1)-1)n+1$ when $(n)_2 = 0$. Similarly, there exists an edge $x_{p_1}^{(i_1)}x_{q_1}^{(j_1)}\in E(\widetilde{G})$ such that $\beta_1(x_{p_1}^{(i_1)}x_{q_1}^{(j_1)}) = w(G)n+2$, since in the coloring $\alpha_1$ there exists an edge $u_{i_1}u_{j_1}\in E(G)$ with $\alpha_1(u_{i_1}u_{j_1}) = w(G)$, and since $\beta_1(x_{2}^{(i_1)}x_{n}^{(j_1)}) = (\alpha_1(u_{i_1}u_{j_1})-1)n+(n+2-3)_n+3 = w(G)n+2$ when $(n)_2 = 1$ and $\beta_1(x_{1}^{(i_1)}x_{n}^{(j_1)}) = (\alpha_1(u_{i_1}u_{j_1})-1)n+(n+1-3)_n+3 = w(G)n+2$ when $(n)_2 = 0$.

Now, by Lemma 1.1, we have that $\beta_1$ is an interval $(w(G)n+2)$-edge coloring of the graph $\widetilde{G}$.

Next, we prove that $W(\widetilde{G})\geq (W(G)+1)n-1$. For this, we define an edge-coloring $\beta_2$ of the graph $\widetilde{G}$ in the following two steps:

Step 1. For every edge $x_{p}^{(i)}x_q^{(j)}\in E(G^{(1)})$, $1\leq p, q\leq n$, let

Step 2. For every edge $x_{p}^{(i)}x_{p+1}^{(i)}\in E(G^{(2)})$, $1\leq p\leq n-1$, let

Let us prove that $\beta_2$ is an interval edge coloring of $\widetilde{G}$.

First, we prove that the set $S(x_{p}^{(i)}, \beta_2)$ is an interval for each vertex $x_{p}^{(i)}\in V(\widetilde{G})$, where $i = 1, \ldots, m$, $p = 1, \ldots, n$.

If $H_i$ is isomorphic to a path, by the definition of $\beta_2$, we have

If $H_i\cong \overline{K_n}$, by the definition of $\beta_2$, we have

Second, note that

Clearly, we have

This implies that $\beta_2$ is a proper edge coloring of $\widetilde{G}$.

Finally, we show that in the coloring $\beta_2$, all colors are used. Clearly, there exists an edge $x_{p_0}^{(i_0)}x_{p_0+1}^{(i_0)}\in E(\widetilde{G})$ such that $\beta_2(x_{p_0}^{(i_0)}x_{p_0+1}^{(i_0)}) = 1$, since in the coloring $\alpha_2$ there exists a vertex $u_{i_0}$ such that $\tau_{i_0}(\alpha_2) = 1$, and since $\beta_2(x_{1}^{(i_0)}x_{2}^{(i_0)}) = (\tau_{i_0}(\alpha_2)-1)n+1$. Similarly, there exists an edge $x_{p_1}^{(i_1)}x_{q_1}^{(j_1)}\in E(\widetilde{G})$ such that $\beta_2(x_{p_1}^{(i_1)}x_{q_1}^{(j_1)}) = (W(G)+1)n-1$, since in the coloring $\alpha_2$ there exists an edge $u_{i_1}u_{j_1}\in E(G)$ with $\alpha_2(u_{i_1}u_{j_1}) = W(G)$, and since $\beta_2(x_{n-1}^{(i_1)}x_{n}^{(j_1)}) = (\alpha_2(u_{i_1}u_{j_1})-1)n+2n-1 = (W(G)+1)n-1.$

Now, by Lemma 1.1, we have that $\beta_2$ is an interval $((W(G)n+1)n-1)$-edge coloring of the graph $\widetilde{G}$.

Case 2. $\widetilde{G}\in\mathcal{G}_1^2$.

Then Condition I holds and $\lambda = 2$. By Lemma 1.2, we can assume that $\alpha(u_{i_0}u_{j_0}) = 1$. It is easy to see that $w(G)n+2(\lambda)_2+(\lambda+1)_2(n)_2 = w(G)n+(n)_2, (W(G)+1)n-\lambda = (W(G)+1)n-2$.

Now, we prove that $w(\widetilde{G})\leq w(G)n+(n)_2$. For this, we define an edge-coloring $\beta_3$ of the graph $\widetilde{G}$ in the following two steps:

Step 1. For every edge $x_{p}^{(i)}x_q^{(j)}\in E(G^{(1)})$, $1\leq p, q\leq n$, if $(n)_2 = 1$, then let

if $(n)_2 = 0$, then let

Step 2. For every edge $x_{p}^{(i)}x_{p+1}^{(i)}\in E(G^{(2)})$, $1\leq p\leq n-1$, let

Let us prove that $\beta_3$ is an interval $(w(G)n+(n)_2)$-edge coloring of the graph $\widetilde{G}$.

First, for any edge $x_{p}^{(i)}x_q^{(j)}\in E(\widetilde{G})$, by the definitions of colorings $\beta_1$ and $\beta_3$, if $(n)_2 = 1$, then $\beta_3(x_{p}^{(i)}x_q^{(j)}) = \beta_1(x_{p}^{(i)}x_q^{(j)})-1$, otherwise, $\beta_3(x_{p}^{(i)}x_q^{(j)}) = \beta_1(x_{p}^{(i)}x_q^{(j)})-2$. Since $\beta_1$ is an interval edge coloring of $\widetilde{G}$, the coloring $\beta_3$ is a proper edge coloring of $\widetilde{G}$ and the color set of each vertex forms an integer interval.

Next, we show that in the coloring $\beta_3$, all colors are used. Clearly, there exists an edge $x_{p_0}^{(i_0)}x_{q_0}^{(j_0)}\in E(\widetilde{G})$ such that $\beta_3(x_{p_0}^{(i_0)}x_{q_0}^{(j_0)}) = 1$, since in the coloring $\alpha_1$ there exists a vertex $u_{i_0}$ such that $\tau_{i_0}(\alpha_1) = 1$, and since $\beta_3(x_{1}^{(i_0)}x_{1}^{(j_0)}) = (\tau_{i_0}(\alpha_1)-1)n+1$. Similarly, there exists an edge $x_{p_1}^{(i_1)}x_{q_1}^{(j_1)}\in E(\widetilde{G})$ such that $\beta_3(x_{p_1}^{(i_1)}x_{q_1}^{(j_1)}) = w(G)n+(n)_2$, since in the coloring $\alpha_1$ there exists an edge $u_{i_1}u_{j_1}\in E(G)$ with $\alpha_1(u_{i_1}u_{j_1}) = w(G)$, and since $\beta_3(x_{2}^{(i_1)}x_{n}^{(j_1)}) = (w(G)-1)n+n+1 = w(G)n+1$ when $(n)_2 = 1$ and $\beta_3(x_{1}^{(i_1)}x_{n}^{(j_1)}) = \alpha_1(u_{i_1}u_{j_1})n = w(G)n$ when $(n)_2 = 0$.

Now, by Lemma 1.1, we have that $\beta_3$ is an interval $(w(G)n+(n)_2)$-edge coloring of the graph $\widetilde{G}$.

Next, we prove that $W(\widetilde{G})\geq (W(G)+1)n-2$. For this, we define an edge-coloring $\beta_4$ of the graph $\widetilde{G}$ in the following two steps:

Step 1. For every edge $x_{p}^{(i)}x_q^{(j)}\in E(G^{(1)})$, $1\leq p, q\leq n$, let

Step 2. For every edge $x_{p}^{(i)}x_{p+1}^{(i)}\in E(G^{(2)})$, $1\leq p\leq n-1$, let

Let us prove that $\beta_4$ is an interval $((W(G)+1)n-2)$-edge coloring of the graph $\widetilde{G}$.

First, for any edge $x_{p}^{(i)}x_q^{(j)}\in E(\widetilde{G})$, by the definitions of colorings $\beta_2$ and $\beta_4$, we have $\beta_4(x_{p}^{(i)}x_q^{(j)}) = \beta_2(x_{p}^{(i)}x_q^{(j)})-1$. Since $\beta_2$ is an interval edge coloring of $\widetilde{G}$, the coloring $\beta_4$ is a proper edge coloring of $\widetilde{G}$ and the color set of each vertex forms an integer interval.

Next, we show that in the coloring $\beta_4$, all colors are used. Clearly, there exists an edge $x_{p_0}^{(i_0)}x_{q_0}^{(j_0)}\in E(\widetilde{G})$ such that $\beta_4(x_{p_0}^{(i_0)}x_{q_0}^{(j_0)}) = 1$, since in the coloring $\alpha_2$ there exists a vertex $u_{i_0}$ such that $\tau_{i_0}(\alpha_2) = 1$, and since $\beta_4(x_{1}^{(i_0)}x_{1}^{(j_0)}) = (\tau_{i_0}(\alpha_2)-1)n+1$. Similarly, there exists an edge $x_{p_1}^{(i_1)}x_{q_1}^{(j_1)}\in E(\widetilde{G})$ such that $\beta_4(x_{p_1}^{(i_1)}x_{q_1}^{(j_1)}) = (W(G)+1)n-2$, since in the coloring $\alpha_2$ there exists an edge $u_{i_1}u_{j_1}\in E(G)$ with $\alpha_2(u_{i_1}u_{j_1}) = W(G)$, and since $\beta_4(x_{n-1}^{(i_1)}x_{n}^{(j_1)}) = (\alpha_2(u_{i_1}u_{j_1})-1)n+2n-2 = (W(G)+1)n-2.$

Now, by Lemma 1.1, we have that $\beta_4$ is an interval $((W(G)+1)n-2)$-edge coloring of the graph $\widetilde{G}$. □

From Theorem 2.1, one can easily see that if $(n)_2 = 0$ and $H_i\cong \overline{k_n}$, then Theorem 2.1 can obtain the same upper bound on $w(\widetilde{G})$ as Theorem 1.1.

We extend the result of Theorem 1.2 from the lexicographic product of graphs to the generalized lexicographic product of graphs and obtain the following result:

Theorem 2.2. If $\widetilde{G}\in \mathcal{G}_2$, then $\widetilde{G}\in\mathfrak{N}$. Moreover, $w(\widetilde{G})\leq w(G)n+w(H_{k_0})$, $W(\widetilde{G})\geq W(G)n+w(H_{k_0})$.

Proof. For the proof, let $\alpha$ be an interval $t$-coloring of $G$, and we consider the following two cases.

Case 1. $\widetilde{G}\in \mathcal{G}_2^1.$

Then Condition I holds, and by Lemma 1.2, we can assume that $\alpha(u_{i_0}u_{j_0}) = 1$.

Let

Obviously, $\mathcal{C}_1\cap \mathcal{C}_2 = \varnothing$, $\mathcal{C}_3^{(i)}\subseteq\mathcal{C}_2$, and $|\mathcal{C}_3^{(i)}| = w(H_i)$.

Now, we construct an edge coloring $\beta$ of $\widetilde{G}$ as follows.

First, we define the following edge-coloring $\beta_1$ of the graph $G^{(1)}$ with $nt$ colors in $\mathcal{C}_1$. For every edge $x_{p}^{(i)}x_q^{(j)}\in E(G^{(1)})$, $1\leq p, q\leq n$, let

Second, we define the following edge-coloring $\beta_2$ of the graph $G^{(2)}$. If $H_i\cong H_{k_0}$, we color the edges of $H_{k_0}$ with $w(H_{k_0})$ colors in $\mathcal{C}_2$ such that the colors on the edges incident to any vertex are consecutive; if $H_i\not \cong H_{k_0}$, we color the edges of $H_i$ with $w(H_i)$ colors in $\mathcal{C}_3^{(i)}$ such that the colors on the edges incident to any vertex are consecutive.

Finally, for every edge $e\in E(\widetilde{G})$, let

Let us prove that $\beta$ is an interval $(tn+w(H_{k_0}))$-edge coloring of $\widetilde{G}$. It is easy to see that the set $S(x_{p}^{(i)}, \beta)$ is an interval for each vertex $x_{p}^{(i)}\in V(\widetilde{G})$, since both $S(x_{p}^{(i)}, \beta_1)$ and $S(x_{p}^{(i)}, \beta_2)$ are intervals, and since $\min S(x_{p}^{(i)}, \beta_1) = \max S(x_{p}^{(i)}, \beta_2)+1$.

Next, we show that in the coloring $\beta$ all colors are used. Clearly, there exists an edge $x_{p_0}^{(i_0)}x_{q_0}^{(j_0)}\in E(\widetilde{G})$ such that $\beta(x_{p_0}^{(i_0)}x_{q_0}^{(j_0)}) = 1$, since in the coloring $\alpha$ there exists an edge $u_{i_0}u_{j_0}\in E(G)$ with $\alpha(u_{i_0}u_{j_0}) = 1$, and since $\beta(x_{1}^{(i_0)}x_{1}^{(j_0)}) = (\alpha(u_{i_0}u_{j_0})-1)n+1.$ Similarly, there exists an edge $x_{p_1}^{(i_1)}x_{q_1}^{(j_1)}\in E(\widetilde{G})$ such that $\beta(x_{p_1}^{(i_1)}x_{q_1}^{(j_1)}) = tn+w(H_{k_0})$, since in the coloring $\alpha$ there exists an edge $u_{i_1}u_{j_1}\in E(G)$ with $\alpha(u_{i_1}u_{j_1}) = t$, and since $\beta(x_{1}^{(i_1)}x_{n}^{(j_1)}) = \alpha(u_{i_1}u_{j_1})n+w(H_{k_0}) = tn+w(H_{k_0})$.

Therefore, $\beta$ is an interval $(tn+w(H_{k_0})$-edge coloring of $\widetilde{G}$. By the definition of $\beta$, we have $w(\widetilde{G})\leq w(G)n+w(H_{k_0})$, $W(\widetilde{G})\geq W(G)n+w(H_{k_0})$.

Case 2. $\widetilde{G}\in \mathcal{G}_2^2.$

Let

Obviously, $\mathcal{D}_1\cap \mathcal{D}_2 = \varnothing$, $\mathcal{D}_3^{(i)}\subseteq\mathcal{D}_2$, and $|\mathcal{D}_3^{(i)}| = w(H_i)$.

Since $G\in\mathfrak{N}$, there exists an interval $t$-coloring $\alpha$ of $G$. Now, we construct an edge coloring $\beta'$ of $\widetilde{G}$ as follows.

First, we define the following edge-coloring $\beta_3$ of the graph $G^{(1)}$ with $nt$ colors in $\mathcal{D}_1$. For every edge $x_{p}^{(i)}x_q^{(j)}\in E(G^{(1)})$, $1\leq p, q\leq n$, let

Second, we define the following edge-coloring $\beta_4$ of the graph $G^{(2)}$. If $H_i\cong H_{k_0}$, we color the edges of $H_{k_0}$ with $w(H_{k_0})$ colors in $\mathcal{D}_2$ such that the colors on the edges incident to any vertex are consecutive; if $H_i\not \cong H_{k_0}$, we color the edges of $H_i$ with $w(H_i)$ colors in $\mathcal{D}_3^{(i)}$ such that on the edges incident to any vertex are consecutive.

Finally, for every edge $e\in E(\widetilde{G})$, let

It is easy to see that $\beta'$ is an interval $(tn+w(H_{k_0}))$-edge coloring of the graph $\widetilde{G}$. Its proof is similar to the proof of case 1. By the definition of $\beta'$, we have $w(\widetilde{G})\leq w(G)n+w(H_{k_0})$, $W(\widetilde{G})\geq W(G)n+w(H_{k_0})$. □

It is not difficult to see that if $H_i$ is a $r$-regular graph and $H_i\in\mathfrak{N}$ for any $i = 1, \ldots, m$, from Theorem 2.2, we can directly derive Theorem 1.2.

We extend Theorem 1.3 from the lexicographic product of graphs to the generalized lexicographic product of graphs, and obtained the following results:

Theorem 2.3. If $\widetilde{G}\in\mathcal{G}_3$, then $\widetilde{G}\in\mathfrak{N}$. Moreover,

(i) If $\widetilde{G}\in \mathcal{G}_3^1$, then $w(\widetilde{G}) \leq w(G)n+2$, $W(\widetilde{G})\geq W(G)n+\frac{n}{2}+1$;

(ii) If $\widetilde{G}\in \mathcal{G}_3^2$, then $w(\widetilde{G}) \leq w(G)n$, $W(\widetilde{G})\geq W(G)n+\frac{n}{2}-1$.

Proof. For the proof, we consider the following two cases:

Case 1. $\widetilde{G}\in \mathcal{G}_3^1$.

Then Condition I holds, and by Lemma 1.2, we can assume that $\alpha(u_{i_0}u_{j_0}) = 1$. Now, we prove that $w(\widetilde{G})\leq w(G)n+2$. For this, we define an edge-coloring $\beta_1$ of the graph $\widetilde{G}$ in the following two steps:

Step 1. For every edge $x_{p}^{(i)}x_q^{(j)}\in E(G^{(1)})$, $1\leq p, q\leq n$, let

Step 2. For every edge $x_{p}^{(i)}x_{p+1}^{(i)}\in E(G^{(2)})$, $1\leq p\leq n-1$, let

if $H_i$ is isomorphic to a cycle, for the edge $(x_{1}^{(i)}x_{n}^{(i)})\in E(G^{(2)})$, let

Let us prove that $\beta_1$ is an interval edge coloring of the graph $\widetilde{G}$.

First, we prove that the set $S(x_p^{(i)}, \beta_1)$ is an interval for each vertex $x_p^{(i)}\in V(\widetilde{G})$, where $i = 1, \ldots, m$, $p = 1, \ldots, n$.

If $H_i\cong \overline{K_n}$, by the definition of $\beta_1$, we have

If $H_i$ is isomorphic to a path or a cycle, by the definition of $\beta_1$, we have

and when $H_i$ is isomorphic to a path, we have

when $H_i$ is isomorphic to a cycle, we have

Second, note that

Clearly, we have

This implies that $\beta_1$ is a proper edge coloring of $\widetilde{G}$.

Finally, we show that $\beta_1$ all colors are used. Clearly, there exists an edge $x_{p_0}^{(i_0)}x_{p_0+1}^{(i_0)}\in E(\widetilde{G})$ such that $\beta_1(x_{p_0}^{(i_0)}x_{p_0+1}^{(i_0)}) = 1$, since in the coloring $\alpha_1$ there exists a vertex $u_{i_0}$ such that $\tau_{i_0}(\alpha_1) = 1$, and since $\beta_1(x_{1}^{(i_0)}x_{2}^{(i_0)}) = (\tau_{i_0}(\alpha_1)-1)n+1 = 1.$ Similarly, there exists an edge $x_{p_1}^{(i_1)}x_{q_1}^{(j_1)}\in E(\widetilde{G})$ such that $\beta_1(x_{p_1}^{(i_1)}x_{q_1}^{(j_1)}) = w(G)n+2$, since in the coloring $\alpha_1$ there exists an edge $u_{i_1}u_{j_1}\in E(G)$ with $\alpha(u_{i_1}u_{j_1}) = w(G)$, and since $\beta_1(x_{1}^{(i_1)}x_{n}^{(j_1)}) = \alpha(u_{i_1}u_{j_1})n+2 = w(G)n+2.$

Now, by Lemma 1, we have that $\beta_1$ is an interval $(w(G)n+2)$-edge coloring of the graph $\widetilde{G}$.

Now, we prove that $W(\widetilde{G})\geq W(G)n+\frac{n}{2}+1$. For this, we define an edge-coloring $\beta_2$ of the graph $\widetilde{G}$ in the following two steps:

Step 1. For every edge $x_{p}^{(i)}x_q^{(j)}\in E(G^{(1)})$, let

Step 2. For every edge $x_{p}^{(i)}x_{p+1}^{(i)}\in E(G^{(2)})$, $1\leq p\leq n-1$, let

if $H_i$ is isomorphic to a cycle, for the edge $(x_{1}^{(i)}x_{n}^{(i)})\in E(G^{(2)})$, let

Let us prove that $\beta_2$ is an interval $(W(G)n+\frac{n}{2}+1)$-edge coloring of the graph $\widetilde{G}$.

First we prove that the set $S(x_p^{(i)}, \beta_2)$ is an interval for each vertex $x_p^{(i)}\in V(\widetilde{G})$, where $i = 1, \ldots, m$, $p = 1, \ldots, n$.

If $H_i$ is isomorphic to a path or a cycle, by the definition of $\beta_2$, we have

and when $H_i$ is isomorphic to a path, we have

when $H_i$ is isomorphic to a cycle, we have

If $H_i\cong \overline{K_n}$, by the definition of $\beta_2$, we have

Second, note that

Clearly, we have

This implies that $\beta_2$ is a proper edge coloring of $\widetilde{G}$.

Finally, we show that in the coloring $\beta_2$, all colors are used. Clearly, there exists an edge $x_{1}^{(i_0)}x_{n}^{(i_0)}\in E(\widetilde{G})$ such that $\beta_1(x_{1}^{(i_0)}x_{n}^{(i_0)}) = 1$, since in the coloring $\alpha_2$ there exists a vertex $u_{i_0}$ such that $\tau_{i_0}(\alpha_2) = 1$, and since $\beta_2(x_{1}^{(i_0)}x_{n}^{(i_0)}) = (\tau_{i_0}(\alpha_2)-1)n+1$. Similarly, there exists an edge $x_{p_1}^{(i_1)}x_{q_1}^{(j_1)}\in E(\widetilde{G})$ such that $\beta_2(x_{p_1}^{(i_1)}x_{q_1}^{(j_1)}) = W(G)n+\frac{n}{2}+1$, since in the coloring $\alpha_2$ there exists an edge $u_{i_1}u_{j_1}\in E(G)$ with $\alpha_2(u_{i_1}u_{j_1}) = W(G)$, and since $\beta_2(x_{p_1}^{(i_1)}x_{q_1}^{(j_1)}) = (W(G)-1)n+\frac{3n}{2}+1 = W(G)n+\frac{n}{2}+1.$

Now, by Lemma 1.1, we have that $\beta_2$ is an interval $(W(G)n+\frac{n}{2}+1)$-edge coloring of the graph $\widetilde{G}$.

Case 2. $\widetilde{G}\in \mathcal{G}_3^2$.

Now, we prove that $w(\widetilde{G})\leq w(G)n$. For this, we define an edge-coloring $\beta_3$ of the graph $\widetilde{G}$ in the following two steps:

Step 1. For every edge $x_{p}^{(i)}x_q^{(j)}\in E(G^{(1)})$, let

Step 2. For every edge $x_{p}^{(i)}x_{p+1}^{(i)}\in E(G^{(2)})$, $1\leq p\leq n-1$, let

if $H_i$ is isomorphic to a cycle, for the edge $(x_{1}^{(i)}x_{n}^{(i)})\in E(G^{(2)})$, let

Similar to the coloring $\beta_1$ in case 1 to discuss. It is easy to see that $\beta_3$ is an interval $w(G)n$-coloring of $\widetilde{G}$.

Now, we prove that $W(\widetilde{G})\geq W(G)n+\frac{n}{2}-1$. For this, we define an edge-coloring $\beta_4$ of the graph $\widetilde{G}$ in the following two steps:

Step 1. For every edge $x_{p}^{(i)}x_q^{(j)}\in E(G^{(1)})$, $1\leq p, q\leq n$, let

Step 2. For every edge $x_{p}^{(i)}x_{q}^{(i)}\in E(G^{(2)})$, $1\leq p, q\leq n$, let

It is easy to see that $\beta_4$ is an interval $(W(G)n+\frac{n}{2}-1)$-coloring of $\widetilde{G}$. □

It is not difficult to see that if $H_i$ is isomorphic to a cycle for any $i = 1, \ldots, m$, from Theorem 2.3, we can directly derive Theorem 1.3.

From Theorems 2.1–2.3, we can see that $\mathcal{G}_z\subset\mathfrak{N}, z = 1, 2, 3.$

3.   Conclusions

In this paper, we studied the interval edge coloring of the generalized lexicographic product $\widetilde{G}$ of an interval colorable graph $G$ with $m$ vertices and a sequence of vertex-disjoint graphs $h_m = (H_i)_{i\in\{1, \ldots, m\}}$, where each graph in $h_m$ has $n$ vertices, and proved that $\widetilde{G}$ is interval colorable if and only if $h_m = (H_i)_{i\in\{1, \ldots, m\}}$ satisfies one of the following three conditions: (i) each graph $H_i$ in $h_m$ is isomorphic to a path or an empty graph; (ii) each graph $H_i$ in $h_m$ is isomorphic to an empty graph or an interval-colorable regular graph, but not all graphs in $h_m$ are empty graphs; (iii) each graph $H_i$ in $h_m$ is isomorphic to a path or a cycle or an empty graph of even order, and $H_{k_0}$ is a cycle. Moreover, we obtain the bounds on $w(\widetilde{G})$ and $W(\widetilde{G})$.

Author contributions

M. Jin: Writing-original draft preparation; M. Jin, P. Chen and S. Tian: Formal analysis; M. Jin, P. Chen and S. Tian: Writing-review and editing. All authors have read and agreed to the published version of the manuscript.

Acknowledgments

This research was supported by the National Natural Science Foundation of China (12061061) and Applied Mathematics National Minority Committee Key Discipline (11080327). The authors thank the innovation team of operations research and cybernetics at Northwest Minzu University.

Conflict of interest

All authors declare no conflicts of interest in this paper.