Research article Special Issues

Edge-coloring of generalized lexicographic product of graphs

  • Received: 05 March 2024 Revised: 05 April 2024 Accepted: 19 April 2024 Published: 07 May 2024
  • MSC : 05C15

  • 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.

    Citation: Shuangliang Tian, Ping Chen. Edge-coloring of generalized lexicographic product of graphs[J]. AIMS Mathematics, 2024, 9(6): 15988-15995. doi: 10.3934/math.2024774

    Related Papers:

  • 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.



    加载中


    [1] A. G. Chetwynd, A. J. W. Hilton, Regular graphs of high degree are 1-factorizable, Proc. London Math. Soc., 50 (1985), 193–206. https://doi.org/10.1112/plms/s3-50.2.193 doi: 10.1112/plms/s3-50.2.193
    [2] R. Diestel, Graph Theory, Berlin: Springer-Verlag, 2017.
    [3] I. Holyer, The NP-completeness of edge-coloring, SIAM J. Comput., 10 (1981), 718–720. https://doi.org/10.1137/0210055 doi: 10.1137/0210055
    [4] M. M. M. Jaradat, On the Anderson-Lipman conjecture and some related problems, Discrete Math., 297 (2005), 167–173. https://doi.org/10.1016/j.disc.2004.09.012 doi: 10.1016/j.disc.2004.09.012
    [5] B. Mohar, On edge colorability of products of graphs, Publ. Inst. Math., 36 (1984), 13–16.
    [6] C. De Simonea, A. Galluccio, Edge-colouring of joins of regular graphs Ⅰ, J. Comb. Optim., 18 (2009), 417–428. https://doi.org/10.1007/s10878-009-9235-8 doi: 10.1007/s10878-009-9235-8
    [7] C. De Simonea, A. Galluccio, Edge-colouring of joins of regular graphs Ⅱ, J. Comb. Optim., 25 (2013), 78–90. https://doi.org/10.1007/s10878-011-9420-4 doi: 10.1007/s10878-011-9420-4
    [8] C. De Simone, A. Galluccio, Edge-colouring of regular graphs of large degree, Theoret. Comput. Sci., 389 (2007), 91–99. https://doi.org/10.1016/j.tcs.2007.07.046 doi: 10.1016/j.tcs.2007.07.046
    [9] C. De Simonea, C. Picinin de Mello, Edge-colouring of join graphs, Theoret. Comput. Sci., 355 (2006), 364–370. https://doi.org/10.1016/j.tcs.2005.12.010 doi: 10.1016/j.tcs.2005.12.010
    [10] W. Szumny, I. Włoch, A. Włoch, On the existence and on the number of $(k, 1)$-kernels in the lexicographic product of graphs, Discrete Math., 308 (2008), 4616–4624. https://doi.org/10.1016/j.disc.2007.08.078 doi: 10.1016/j.disc.2007.08.078
    [11] D. B. West, Introduction to Graph Theory, 2 Eds., Englewood Cliffs: Prentice-Hall, 2000.
  • Reader Comments
  • © 2024 the Author(s), licensee AIMS Press. This is an open access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0)
通讯作者: 陈斌, bchen63@163.com
  • 1. 

    沈阳化工大学材料科学与工程学院 沈阳 110142

  1. 本站搜索
  2. 百度学术搜索
  3. 万方数据库搜索
  4. CNKI搜索

Metrics

Article views(186) PDF downloads(23) Cited by(0)

Article outline

Figures and Tables

Figures(2)

Other Articles By Authors

/

DownLoad:  Full-Size Img  PowerPoint
Return
Return

Catalog