Back to Search
Start Over
Edge-coloring of generalized lexicographic product of graphs
- Source :
- AIMS Mathematics, Vol 9, Iss 6, Pp 15988-15995 (2024)
- Publication Year :
- 2024
- Publisher :
- AIMS Press, 2024.
-
Abstract
- 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. The chromatic index of $ G $, denoted by $ \chi'(G) $, is the least $ k $ for which $ G $ has a $ k $ edge-coloring. Graphs with $ \chi'(G) = \Delta(G) $ are said to be Class 1, and graphs with $ \chi'(G) = \Delta(G)+1 $ are said to be Class 2. 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) $. If $ G $ is a complete graph with order 2, then $ G[h_2] $ denotes a join $ H_1+H_2 $ of vertex-disjoint graphs $ H_1 $ and $ H_2 $. If $ H_i\cong H $ for $ i = 1, 2, \ldots, n $, then $ G[h_n] = G[H] $, where $ G[H] $ denotes the lexicographic product of two graphs $ G $ and $ H $. In this paper, we provide sufficient conditions for the generalized lexicographic product $ G[h_n] $ of $ G $ and $ h_n = (H_i)_{i\in\{1, 2, \ldots, n\}} $ to be Class 1, where all graphs in $ h_n $ have the same number of vertices.
- Subjects :
- edge-coloring
decomposition
generalized lexicographic product
Mathematics
QA1-939
Subjects
Details
- Language :
- English
- ISSN :
- 24736988
- Volume :
- 9
- Issue :
- 6
- Database :
- Directory of Open Access Journals
- Journal :
- AIMS Mathematics
- Publication Type :
- Academic Journal
- Accession number :
- edsdoj.1ff13a1dd1a648bbb2eccce8eb278712
- Document Type :
- article
- Full Text :
- https://doi.org/10.3934/math.2024774?viewType=HTML