TY - JOUR
AU - Kamalian , Rafayel R.
AU - Petrosyan, Petros A.
PY - 2021/12/10
Y2 - 2024/05/22
TI - A Note on Interval Edge-colorings of Graphs
JF - Mathematical Problems of Computer Science
JA - MPCS
VL - 36
IS -
SE - Articles
DO -
UR - http://mpcs.sci.am/index.php/mpcs/article/view/261
SP - 13-16
AB - <p>An edge-coloring of a graph G with colors 1,…,t is called an interval t-coloring if for all colors are used, and the colors of edges incident to each vertex of G are distinct and form an interval of integers. In this note we prove that if a connected graph G with n vertices admits an interval t-coloring, then t≤2n - 3. We also show that if G is a connected r-regular graph with n vertices that has an interval t-coloring and n≥2r + 2, then this upper bound can be improved to 2n - 5.</p>
ER -