An edge-coloring of a graph $ G $ with colors $ 1, \ldots, t $ is an interval $ t $-coloring if all colors are used and the colors of edges incident to each vertex of $ G $ are distinct and form an interval of integers. A graph $ G $ is interval colorable if it has an interval $ t $-coloring for some positive integer $ t $. For an interval colorable graph $ G $, the least and the greatest values of $ t $ for which $ G $ has an interval $ t $-coloring are denoted by $ w(G) $ and $ W(G) $. 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) $. In this paper, we obtain several sufficient conditions for the generalized lexicographic product $ G[h_m] $ to have interval colorings. We also present some sharp bounds on $ w(G[h_m]) $ and $ W(G[h_m]) $ of $ G[h_m] $.
Citation: Meiqin Jin, Ping Chen, Shuangliang Tian. Interval edge colorings of the generalized lexicographic product of some graphs[J]. AIMS Mathematics, 2024, 9(11): 30597-30611. doi: 10.3934/math.20241477
An edge-coloring of a graph $ G $ with colors $ 1, \ldots, t $ is an interval $ t $-coloring if all colors are used and the colors of edges incident to each vertex of $ G $ are distinct and form an interval of integers. A graph $ G $ is interval colorable if it has an interval $ t $-coloring for some positive integer $ t $. For an interval colorable graph $ G $, the least and the greatest values of $ t $ for which $ G $ has an interval $ t $-coloring are denoted by $ w(G) $ and $ W(G) $. 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) $. In this paper, we obtain several sufficient conditions for the generalized lexicographic product $ G[h_m] $ to have interval colorings. We also present some sharp bounds on $ w(G[h_m]) $ and $ W(G[h_m]) $ of $ G[h_m] $.
[1] | A. S. Asratian, R. R. Kamalian, Interval colorings of edges of a multigraph, Appl. Math., 5 (1987), 25–34. https://doi.org/10.48550/arXiv.1401.8079 doi: 10.48550/arXiv.1401.8079 |
[2] | A. S. Asratian, C. J. Casselgren, On interval edge colorings of $(\alpha, \beta)$-biregular bipartite graphs, Discrete Math., 307 (2007), 1951–1956. https://doi.org/10.1016/j.disc.2006.11.001 doi: 10.1016/j.disc.2006.11.001 |
[3] | J. A. Bondy, U. S. R. Murty, Graph theory with applications, London: Macmillan, 1976. |
[4] | K. Giaro, M. Kubale, M. Małafiejski, Consecutive colorings of the edges of general graphs, Discrete Math., 236 (2001), 131–143. https://doi.org/10.1016/S0012-365X(00)00437-4 doi: 10.1016/S0012-365X(00)00437-4 |
[5] | A. Grzesik, H. Khachatrian, Interval edge-colorings of $K_{1, m, n}$, Discrete Appl. Math., 174 (2014), 140–145. https://doi.org/10.1016/j.dam.2014.04.003 doi: 10.1016/j.dam.2014.04.003 |
[6] | H. M. Hansen, Scheduling with minimum waiting periods, Master's Thesis, Odense University, Denmark, 1992. |
[7] | 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 |
[8] | P. Jing, Z. Miao, Z. X. Song, Some remarks on interval colorings of complete tripartite and biregular graphs, Discrete Appl. Math., 277 (2020), 193–197. https://doi.org/10.1016/j.dam.2019.08.024 doi: 10.1016/j.dam.2019.08.024 |
[9] | R. R. Kamalian, Interval colorings of complete bipartite graphs and trees, Preprint of the Computing Centre of the Academy of Sciences of Armenia, 1989. https://doi.org/10.48550/arXiv.1308.2541 |
[10] | R. R. Kamalian, Interval edge colorings of graphs, Doctoral Thesis, Novosibirsk, 1990. |
[11] | R. R. Kamalian, P. A. Petrosyan, A note on upper bounds for the maximum span in interval edge-colorings of graphs, Discrete Math., 312 (2012), 1393–1399. https://doi.org/10.1016/j.disc.2012.01.005 |
[12] | P. A. Petrosyan, Interval edge-colorings of Möbius ladders, In: Proceedings of the CSIT Conference, 2005,146–149. https://doi.org/10.48550/arXiv.0801.0159 |
[13] | P. A. Petrosyan, Interval edge-colorings of complete graphs and $n$-dimensional cubes, Discrete Math., 310 (2010), 1580–1587. doi:10.1016/j.disc.2010.02.001 |
[14] | P. A. Petrosyan, Interval edge colorings of some products of graphs, Discuss. Math. Graph T., 31 (2011), 357–373. |
[15] | P. A. Petrosyan, H. H. Khachatrian, L. E. Yepremyan, H. G. Tananyan, Interval edge-colorings of graph products, In: Proceedings of the CSIT Conference, 2011, 89–92. https://doi.org/10.48550/arXiv.1110.1165 |
[16] | S. V. Sevastjanov, Interval colorability of the edges of a bipartite graph, Metody Diskretnogo Analiza, 50 (1990), 61–72. |
[17] | V. Samodivkin, Domination related parameters in the generalized lexicographic product of graphs, Discrete Appl. Math., 300 (2021), 77-84. https://doi.org/10.1016/j.dam.2021.03.015 doi: 10.1016/j.dam.2021.03.015 |
[18] | H. H. Tepanyan, P. A. Petrosyan, Interval edge-colorings of composition of graphs, Discrete Appl. Math., 217 (2017), 368–374. https://doi.org/10.1016/j.dam.2016.09.022 doi: 10.1016/j.dam.2016.09.022 |
[19] | V. G. Vizing, On an estimate of the chromatic class of a p-graph, Discret Analiz, 3 (1964), 25–30. |