Edge-coloring of generalized lexicographic product of graphs

1.   Introduction

In this paper, we consider only undirected, connected, and simple graphs. We use $V(G)$ and $E(G)$ to denote the vertex set and the edge set of a graph $G$, respectively.

An edge-coloring of a graph $G$ is an assignment of colors to its edges so that no two edges incident to the same vertex receive the same color. An edge-coloring $\sigma$ of $G$ using $k$ colors ($k$ edge-coloring) is then a partition of the edge set $E(G)$ into $k$ disjoint matchings and it can be written as $\sigma = (M_1, M_2, \ldots, M_{k})$, where every $M_i$ is a matching of $G$. The chromatic index of $G$, denoted by $\chi'(G)$, is the least $k$ for which $G$ has a $k$ edge-coloring. The Vizing Theorem 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. It is NP-complete to determine whether a graph is Class 1 ^[3]. The classification problem is extremely difficult even for regular graphs. For this problem, Chetwynd and Hilton ^[1] proposed the following conjecture:

Conjecture 1.1 (1-Factorization Conjecture). Let $G$ be a $k$-regular graph with $n$ vertices, $n$ even. If $k \geq \frac{n}{2}$ then $\chi'(G) = k$.

In this paper, we consider the generalized lexicographic product of graphs, which is defined as follows ^[10]: Let $G$ be a graph with $V(G) = \{t_1, t_2, \ldots, t_n\}$, $n\geq2$, and $h_n = (H_i)_{i\in\{1, 2, \ldots, n\}}$ be a sequence of vertex-disjoint graphs with $V(H_i) = \{(t_i, y_1), (t_i, y_2), \ldots, (t_i, y_{m_i})\}$, $m_i\geq1$. The generalized lexicographic product $G[h_n]$ of $G$ and $h_n = (H_i)_{i\in\{1, 2, \ldots, n\}}$ is a simple graph with vertex set $\bigcup_{i = 1}^{n}V(H_i)$, in which $(t_i, y_p)$ is adjacent to $(t_j, y_q)$ if and only if either $t_i = t_j$ and $(t_i, y_p)(t_i, y_q)\in E(H_i)$ or $t_it_j\in E(G)$. A generalized lexicographic product is also called an expansion or composition (see^[11]).

By $V_i$, $i = 1, 2, \ldots, n$ we will denote the vertex set of graph $H_i$ in $G[h_n]$, and call the sets $V_1, V_2, \ldots, V_n$ the partition sets of $G[h_n]$. If $H_i\cong H$ for $i = 1, 2, \ldots, n$, then $G[h_n] = G[H]$, where $G[H]$ is the lexicographic product of two graphs $G$ and $H$. For example, the join $H_1+H_2$ of vertex-disjoint graphs $H_1$ and $H_2$ is $K_2[h_2]$, where $h_2 = (H_i)_{i\in\{1, 2\}}$. In addition, Turán graphs $T^{r-1}(n)$ (see^[2]) are complete $(r-1)$-partite graphs with $n\geq r-1$ vertices whose partition sets differ in size by at most 1, that is, $T^{r-1}(n)$ are $K_{r-1}[h_{r-1}]$, where $h_{r-1} = (H_i)_{i\in\{1, 2, \ldots, r-1\}}$ is a sequence of vertex-disjoint empty graphs with $\lfloor\frac{n}{r-1}\rfloor$ vertices or $\lceil\frac{n}{r-1}\rceil$ vertices.

De Simone and Picinin de Mello ^[9] gave the following sufficient conditions for a join graph to be Class 1:

Theorem 1.1. Let $G = H_1+H_2$ be a join graph with $|V(H_1)|\leq |V(H_2)|$. If $\Delta(H_1) > \Delta(H_2)$, then $G$ is Class 1.

Theorem 1.2. Let $G = H_1+H_2$ be a join graph with $\Delta(H_1) = \Delta(H_2)$. If both $H_1$ and $H_2$ are Class 1, or if $H_1$ is a subgraph of $H_2$, or if both $H_1$ and $H_2$ are disjoint unions of cliques, then $G$ is Class 1.

Theorem 1.3. Every regular join graph $G = H_1+H_2$ with $\Delta(H_1) = \Delta(H_2)$ is Class 1.

De Simone and Galluccio ^[8] showed that 1-Factorization Conjecture is true for graphs that are join of two graphs:

Theorem 1.4. Every regular join graph with even order is Class1.

De Simone and Galluccio ^[6,7] extended the above result, and proved the following conclusions:

Theorem 1.5. Every even graph that is the join of two regular graphs is Class 1.

Mohar ^[5] and Jaradat ^[4] gave the following sufficient conditions for a lexicographic product of graphs to be Class 1:

Theorem 1.6. Let $G$ and $H$ be two graphs. If $G$ is Class 1, then $G[H]$ is Class 1.

Theorem 1.7. Let $G$ and $H$ be two graphs. If $\chi'(H) = \Delta(H)$ and $H$ is of even order, then $\chi'(G[H]) = \Delta(G[H])$.

By Theorems 1.6 and 1.7, it is easy to see that for any two regular graphs $G$ and $H$, if 1-Factorization Conjecture is true for the graph $G$, or 1-Factorization Conjecture is true for the graph $H$ and $\Delta(G)\geq \frac{|V(G)|-1}{2}$, then this conjecture is also true for graphs that are lexicographic product $G[H]$ of $G$ and $H$.

In this paper, our goal is to find sufficient conditions for a generalized lexicographic product $G[h_n]$ of $G$ and $h_n = (H_i)_{i\in\{1, 2, \ldots, n\}}$ to be Class 1, where $G$ is a graph with $n$ vertices and all graphs in $h_n$ have the same number of vertices.

The following lemma will be used later:

Lemma 1. (Jaradat^[8])Let $G$ and $H$ be two graphs such that $\chi'(H) = \Delta(H)$. Then $\chi'(G\times H) = \Delta(G\times H)$, where $G\times H$ denotes the direct product of graphs $G$ and $H$.

In Section 2, we shall present two decompositions of the edge set in the generalized lexicographic product of graphs.

2.   The decompositions

Let $G$ be a graph with $V(G) = \{t_1, t_2, \ldots, t_n\}$, $n\geq2$, and $h_n = (H_i)_{i\in\{1, 2, \ldots, n\}}$ be a sequence of vertex-disjoint graphs with $V(H_i) = \{(t_i, y_1), (t_i, y_2), \ldots, (t_i, y_{m})\}$, $m\geq1$. Let $G^{*} = G[h_n]$, and let $U_j = \{(t_1, y_j), (t_2, y_j), \ldots, (t_n, y_j)\}$, where $j = 1, 2, \ldots, m.$ Then $G_j = G^{*}[U_j]\cong G$ for each $j = 1, 2, \ldots, m.$ We will provide two decompositions of the generalized lexicographic product $G^{*}$.

We first consider the case where $G$ is a Class 1 graph and provide a decomposition of $G^{*}$ with respect to a matching of $G$. If there exists a matching $M$ in $G$ such that $\chi'(G-M) = \Delta(G)-1$ and any distinct vertices with the maximum degree of $G$ are saturated by distinct edges of $M$, then $G$ is said to be Subclass 1; otherwise, $G$ is said to be Subclass 2. For example, every Class 1 graph in which no two vertices of maximum degree are adjacent is Subclass 1, and every regular Class 1 graph is Subclass 2.

For every matching $M$ of $G$ such that $\chi'(G-M) = \Delta(G)-1$, let $G_{M}$ denote the subgraph of $G$ induced by $M$. Moreover, let

where $V_{\Delta}$ denotes the set of vertices with the maximum degree in $G$, $\overline{K}_m$ denotes an empty graph with $m$ vertices, and $G_1 = G-{M}$. Then $G^{*}$ is the union of edge-disjoint graphs $G^{*}_{M}$ and $G_1^{*}$, that is,

Figure 1 shows a Subclass 1 graph $G$ and the decomposition of $G^{*} = G[h_5]$ with respect to a matching $M$ in $G$, where $h_n = (H_i)_{i\in\{1, 2, \ldots, 5\}}$ is a sequence of vertex-disjoint graphs, each with $m$ vertices. Figure 2 shows a Subclass 2 graph $G$ and the decomposition of $G^{*} = G[h_6]$ with respect to a matching $M$ in $G$, where $h_n = (H_i)_{i\in\{1, 2, \ldots, 6\}}$ is a sequence of vertex-disjoint graphs, each with $m$ vertices.

We now provide another decomposition of $G^{*}$. Let

Then the graph $G^{*}$ is the union of edge-disjoint graphs $G^{*}_2$ and $G^{*}_3$, that is,

In Section 3, we shall study sufficient conditions for $G^{*}$ to be Class 1 using the above two decompositions of $G^{*}$.

3.   Sufficient conditions for $G[h_n]$ to be Class 1

Through the decomposition of $G^{*}$ in formula 2.1, we can make the following observation:

Observation 3.1. Let $G$ be a Class 1 graph. If there exists a matching $M$ in $G$ such that $\chi'(G-M) = \Delta(G)-1$ and the corresponding $G^{*}_{M}$ is Class 1, then $G^{*}$ is also Class 1.

Proof. Let $M$ be a matching of $G$ such that $\chi'(G-M) = \Delta(G)-1$ and the corresponding $G^{*}_{M}$ is Class 1. It is easy to see that $\Delta(G^{*}_{M}) = \max\{\Delta(H_i)|t_i\in V_{\Delta}\}+m$ and $\Delta(G_1^{*}) = (\Delta(G)-1)m$. Note that $\Delta(G^{*}) = \max\{\Delta(H_i)|t_i\in V_{\Delta}\}+\Delta(G)m$. Hence, $\Delta(G^{*}) = \Delta(G^{*}_{M})+\Delta(G_1^{*})$. It follows that if both $G^{*}_{M}$ and $G_1^{*}$ are Class 1, then $G^{*}$ is Class 1. Thus, we only need to verify that $\chi'(G_1^{*}) = (\Delta(G)-1)m$.

Since $\chi'(G_1) = \Delta(G)-1$, it follows that we can color the edges of $G_1[\overline{K}_m]$ with $(\Delta(G)-1)m$ colors such that for each positive integer $i$, $t_i\in V(G)-V_{\Delta}$, there are at least $m$ colors are missing at all vertices in $V_i$. Note that $G_1^{*} = G_1[\overline{K}_m]\cup(\bigcup_{t_i\in V(G)- V_{\Delta}}H_i)$. Hence, we can extend the $(\Delta(G)-1)m$ edge-coloring of $G_1[\overline{K}_m]$ to all the edges of $\bigcup_{t_i\in V(G)- V_{\Delta}}H_i$, so that $\chi'(G_1^{*}) = (\Delta(G)-1)m$. □

Theorem 3.1. If $G$ is Subclass 1, then there exists a matching $M$ in $G$ such that $\chi'(G-M) = \Delta(G)-1$ and the corresponding $G^{*}_{M}$ is Class 1.

Proof. Let $M$ be a matching of $G$ such that $\chi'(G-M) = \Delta(G)-1$ and any distinct vertices with the maximum degree in $G$ are saturated by distinct edges of $M$. Note that each connected component of $G^{*}_{M}$ is either a join of a graph on $m$ vertices and an empty graph on $m$ vertices, or a balanced complete bipartite graph on $2m$ vertices. It is easy to see that these connected components are all Class 1. Thus $G^{*}_{M}$ is Class 1. □

An instant corollary of Theorem 3.1 and Observation 3.1 is:

Corollary 3.1. If $G$ is Subclass 1, then $G^{*}$ is Class 1.

Theorem 3.2. Let $G$ be a Subclass 2 graph, and let $M$ be a matching of $G$ such that $\chi'(G-M) = \Delta(G)-1$. For every pair of vertices $t_p$ and $t_q$ of maximum degree in $G$ which are saturated by the same edge of $M$, if one of the following five conditions holds:

(i) both $H_p$ and $H_q$ are Class 1;

(ii) $H_p$ is a subgraph of $H_q$;

(iii) both $H_p$ and $H_q$ are disjoint unions of cliques;

(iv) $\Delta(H_p)\not = \Delta(H_q)$;

(v) join graph $H_p+H_q$ is regular;

then $G^{*}_{M}$ is Class 1.

Proof. Since $G$ is Subclass 2, every connected component of $G^{*}_{M}$ can be denoted by $H_p+H_q$, or $H_p+\overline{K}_m$, or $H_q+\overline{K}_m$, or $\overline{K}_m+\overline{K}_m$, where $\overline{K}_m$ denotes an empty graph on $m$ vertices, and $\overline{K}_m+\overline{K}_m$ denotes the join of two vertex-disjoint empty graphs on $m$ vertices. Note that $H_p+\overline{K}_m$, $H_q+\overline{K}_m$ and $\overline{K}_m+\overline{K}_m$ are all Class 1. Hence, it is only necessary to prove that: if one of the conditions (ⅰ)–(ⅴ) holds, then $H_p+H_q$ is Class 1.

Assume that one of the conditions (ⅰ)–(ⅳ) holds. Since $|V(H_p)| = |V(H_q)| = m$, it follows from Theorems 1.1 and 1.2 that $H_p+H_q$ is Class 1.

Assume that (ⅴ) holds. Since $H_p+H_q$ is regular and $|V(H_p)| = |V(H_q)|$, $H_p+H_q$ is Class 1 by Theorem 1.3 or Theorem 1.4. □

An instant corollary of Theorem 3.2 and Observation 3.1 is:

Corollary 3.2. Let $G$ be a Subclass 2 graph, and let $M$ be a matching of $G$ such that $\chi'(G-M) = \Delta(G)-1$. For every pair of vertices $t_p$ and $t_q$ of maximum degree in $G$ which are saturated by the same edge of $M$, if one of five conditions of Theorem 3.2 holds, then $G^{*}$ is Class 1.

Note that the join graph $H_1+H_2$ corresponds to $P_2[h_2]$, where $P_2$ is a Class 1 graph. By Corollaries 3.1 and 3.2, we can effortlessly generalize the results of Theorem 1.5 in the case where $|V(H_1)| = |V(H_2)|$ to the generalized lexicographic product, yielding the following theorem:

Theorem 3.3. If $G$ is Class 1 and all graphs in $h_n$ are regular, then $G^{*}$ is Class 1.

In addition, by Corollaries 3.1 and 3.2, we can directly obtain Theorem 1.6. Furthermore, one easy consequence of Corollary 3.2 is the following result, which is similar to Theorem 1.2.

Theorem 3.4. Let $G = H_1 + H_2$ be a join graph with $|V(H_1)| = |V(H_2)|$. If $G$ is regular, or if both $H_1$ and $H_2$ are Class 1, or if $H_1$ is a subgraph of $H_2$, or if both $H_1$ and $H_2$ are disjoint unions of cliques, then $G$ is Class 1.

Through the decomposition of $G^{*}$ in formula 2.2, we can make the following observation:

Observation 3.2. Suppose that all graphs in $h_n$ have the same maximum degree. If both $G^{*}_2$ and $G_3^{*}$ are Class 1, then $G^{*}$ is Class 1.

Proof. Let $\Delta(H_i) = \Delta_H$, where $i = 1, 2, \ldots, n$. It is easy to see that $\Delta(G^{*}_2) = \Delta(G)+\Delta_H$, $\Delta(G^{*}_3) = \Delta(G)(m-1)$ and $\Delta(G^{*}) = \Delta(G)m+\Delta_H$. Hence, $\Delta(G^{*}) = \Delta(G^{*}_2)+\Delta(G^{*}_3)$. Since $\chi'(G^{*}_2) = \Delta(G^{*}_2)$, and since $\chi'(G^{*}_3) = \Delta(G^{*}_3)$, it follows that $\chi'(G^{*}) = \Delta(G^{*})$, that is, $G^{*}$ is Class 1.□

By Observation 3.2, we can obtain the following theorem:

Theorem 3.5. Suppose that all graphs in $h_n$ are Class 1 graphs with the same maximum degree. If $m$ is even, then $G^{*}$ is Class 1.

Proof. Let $\Delta(H_i) = \Delta_H$, where $i = 1, 2, \ldots, n$. We can first color the edges of each subgraph $G_j$ of $G^{*}_2$ with $\Delta(G)+1$ colors $1, 2, \ldots, \Delta(G)+1$ such that edges which are corresponding to the same edge of $G$ receive the same color. Since we use $\Delta(G)+1$ colors, it follows that each vertex $(t_i, y_j)$ of $H_i$ misses at least one color $c_i$ in $\{1, 2, \ldots, \Delta(G)+1\}$, where $i = 1, 2, \ldots, n.$ Hence, we can color the edges of each subgraph $H_i$ of $G^{*}_2$ with the color $c_i$ and an additional $\Delta_H-1$ new colors. Thus, $\chi'(G^{*}_2)\leq\Delta(G)+\Delta_H = \Delta(G^{*}_2)$, that is, $G^{*}_2$ is Class 1. On the other hand, since $G^{*}_3 = G\times K_m$, and since $m$ is even, $G^{*}_3$ is Class 1 according to Lemma 1.1. Therefore, $G^{*}$ is also Class 1.□

An instant corollary of Theorem 3.5 is:

Corollary 3.3. If all graphs in $h_n$ are regular Class 1 graphs with the same maximum degree, then $G^{*}$ is Class 1.

By applying Theorem 3.5, we can derive Theorem 1.7. Furthermore, by utilizing Theorem 3.3 and Corollary 3.3, we can formulate the following theorem:

Theorem 3.6. Suppose that $G^{*} = G[h_n]$ is regular. If $G$ is Class 1, or each graph of $h_n$ is Class 1, then $G^{*}$ is Class 1.

Proof. Since $G^{*}$ is regular, and since all graphs in $h_n$ have the same number of vertices, it follows that all graphs in $h_n$ are regular graphs with the same maximum degree. If $G$ is Class 1, then $G^{*}$ is Class 1 by Theorem 3.3. If each graph of $h_n$ is Class 1, then $G^{*}$ is Class 1 according to Corollary 3.3. □

By applying Theorem 3.6, take $G = P_2$, we can derive the result of theorem 1.4 in the case where $|V(H_1)| = |V(H_2)|$. In addition, the graph $G^{*}$ in Theorem 3.6 does not necessarily satisfy the condition "$\Delta(G^{*})\geq \frac{|V(G^{*})|}{2}$" of 1-Factorization Conjecture. For instance, suppose that $G$ is a $k$-regular bipartite graph with $n$ vertices, and $h_n = (H_i)_{i\in\{1, 2, \ldots, n\}}$ represents a sequence of vertex-disjoint cubic graphs, each with $m$ vertices, where $m\geq4$. Clearly, $G^{*}$ is Class 1 according to Theorem 3.6, however, we have $\Delta (G^{*}) = km+3 < \frac{nm}{2} = \frac{|V(G^{*})|}{2}$ when $k < \frac{n}{2}-1$.

It is easy to see that if $G^{*}$ is regular and all graphs in $h_n$ have the same number of vertices, then the inequality $\Delta(G^{*})\geq \frac{|V(G^{*})|}{2}$ can be derived from the inequality $\Delta(G)\geq \frac{|V(G)|}{2}$. By Theorem 3.6, if the 1-factorial conjecture holds for $G$, then the conjecture holds for $G^{*}$.

Finally, in a generalized lexicographic product $K_p[h_p]$, we consider the case where $|V(K_p[h_p])|$ is even and every graph in the sequence $h_p = (H_i)_{i\in\{1, 2, \ldots, p\}}$ has $\lfloor\frac{|V(K_p[h_p])|}{p}\rfloor$ vertices or $\lceil\frac{|V(K_p[h_p])|}{p}\rceil$ vertices. Using Theorem 1.5, we can derive the following theorem:

Theorem 3.7. Let $G = K_p[h_p]$ and let $h_p = (H_i)_{i\in\{1, 2, \ldots, p\}}$ be a sequence of vertex-disjoint $k$-regular graphs such that every graph in $h_p$ has $\lfloor\frac{|V(G)|}{p}\rfloor$ vertices or $\lceil\frac{|V(G)|}{p}\rceil$ vertices, where $p\geq 2$ and $k\geq 0$. If $|V(G)|$ is even, then $G$ is Class 1.

Proof. Let $n = |V(G)|$, and let $V_1, V_2, \ldots, V_p$ be the partition sets of $G$. If $\lfloor\frac{n}{p}\rfloor = \lceil\frac{n}{p}\rceil$, it follows that $G$ is an even graph that is the join of two regular graphs, then $G$ is Class 1 according to Theorem 1.5. If $\lfloor\frac{n}{p}\rfloor\not = \lceil\frac{n}{p}\rceil$, then we may assume that $|V_i| = \lfloor\frac{n}{p}\rfloor$ for $i = 1, 2, \ldots, r$ and $|V_i| = \lceil\frac{n}{p}\rceil$ for $i = r+1, r+2, \ldots, p$, where $1\leq r\leq p-1$. Let

Clearly, both $G_1$ and $G_2$ are regular graphs, and $G = G_1+G_2$. By Theorem 1.5, $G$ is Class 1. □

In Theorem 3, 7, by letting $k = 0$ and $p = r-1$, then we can directly derive the following corollary:

Corollary 3.4. All Turán graphs on an even number of vertices are Class 1.

4.   Conclusions

In this paper, for a generalized lexicographic product $G[h_n]$ of a graph $G$ with $n$ vertices and a sequence $h_n = (H_i)_{i\in\{1, 2, \ldots, n\}}$ of vertex-disjoint graphs with $m$ vertices, we obtain the following sufficient conditions for $G[h_n]$ to be Class 1: (ⅰ) $G$ is Subclass 1; (ⅱ) $G$ is Class 1 and all graphs in $h_n$ are regular; (ⅲ) all graphs in $h_n$ are Class 1 graphs with the same maximum degree, and $m$ is even; (ⅳ) $G[h_n]$ is regular and either $G$ or each graph in $h_n$ is Class 1.

In addition, for a generalized lexicographic product $G = K_p[h_p]$ of a complete graph $K_p$ on $p$ vertices and a sequence $h_p = (H_i)_{i\in\{1, 2, \ldots, p\}}$ of vertex-disjoint $k$-regular graphs whose partition sets differ in size by at most 1, we prove that $G$ is Class 1 if $G$ has an even number of vertices.

Use of AI tools declaration

The authors declare that they have not used Artificial Intelligence (AI) tools in the creation of this article.

Acknowledgments

Fund projects: Mathematics, Gansu Province Key Discipline (11080318). Applied Mathematics National Minority Committee Key Discipline (11080327), and Support for innovation team of operations research and Cybernetics in Northwest University for Nationalities.

Conflict of interest

All authors declare no conflicts of interest in this paper.