Interval Edge-Colorings of Cartesian Products of Graphs II
Bulletin of the Malaysian Mathematical Sciences Society · 2026-06 · 49 (3)
DOI: 10.1007/s40840-026-02096-4 ↗Kurz gefasst
Fachartikel in der Zeitschrift Bulletin of the Malaysian Mathematical Sciences Society, online erschienen am 26.05.2026. Verfasst von Petros A. Petrosyan und 2 weiteren Autor:innen. Die Arbeit nennt 32 Literaturangaben.
Abstract (Originalsprache)
An intervalt-coloring of a graph G is a proper edge-coloring with colors 1,⋯,t\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$1,\dots ,t$$\end{document} such that the colors on the edges incident to every vertex of G are colored by consecutive colors. A graph G is called interval colorable if it has an interval t-coloring for some positive integer t. Let N\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\mathfrak {N}$$\end{document} be the set of all interval colorable graphs. For a graph G∈N\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G\in \mathfrak {N}$$\end{document}, we denote by w(G) and W(G) the minimum and maximum number of colors in an interval coloring of a graph G, respectively. In this paper we present some new sharp bounds on W(G□H)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$W(G\square H)$$\end{document} for graphs G and H satisfying various conditions. In particular, we show that if G,H∈N\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$G,H\in \mathfrak {N}$$\end{document} and H is an r-regular (r∈N\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$r\in \mathbb {N}$$\end{document}) graph, then W(G□H)≥W(G)+W(H)+r\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$W(G\square H)\ge W(G)+W(H)+r$$\end{document}. We also derive a new upper bound on W(G) for interval colorable connected graphs with additional distance conditions. Based on these bounds, we improve known lower and upper bounds on W(C2n1□C2n2□⋯□C2nk)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$W(C_{2n_{1}}\square C_{2n_{2}}\square \cdots \square C_{2n_{k}})$$\end{document} for k-dimensional tori C2n1□C2n2□⋯□C2nk\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$C_{2n_{1}}\square C_{2n_{2}}\square \cdots \square C_{2n_{k}}$$\end{document} and on W(K2n1□K2n2□⋯□K2nk)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$W(K_{2n_{1}}\square K_{2n_{2}}\square \cdots \square K_{2n_{k}})$$\end{document} for Hamming graphs K2n1□K2n2□⋯□K2nk\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$K_{2n_{1}}\square K_{2n_{2}}\square \cdots \square K_{2n_{k}}$$\end{document}, and these new bounds coincide with each other for hypercubes. Finally, we give several results on interval colorings of Fibonacci cubes Γn.\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\varGamma _{n}.$$\end{document}
Zitieren
APA
Petrosyan, P. A., Khachatrian, H. H., & Tananyan, H. G. (2026). Interval Edge-Colorings of Cartesian Products of Graphs II. Bulletin of the Malaysian Mathematical Sciences Society, 49(3). https://doi.org/10.1007/s40840-026-02096-4
Vancouver
Petrosyan PA, Khachatrian HH, Tananyan HG. Interval Edge-Colorings of Cartesian Products of Graphs II. Bulletin of the Malaysian Mathematical Sciences Society. 2026;49(3). doi:10.1007/s40840-026-02096-4
BibTeX
@article{Petrosyan2026,
author = {Petrosyan, Petros A. and Khachatrian, Hrant H. and Tananyan, Hovhannes G.},
title = {Interval Edge-Colorings of Cartesian Products of Graphs II},
journal = {Bulletin of the Malaysian Mathematical Sciences Society},
year = {2026},
volume = {49},
number = {3},
doi = {10.1007/s40840-026-02096-4}
}
EUVIMED