A Note on Interval Edge-colorings of Graphs
Rafayel R. Kamalian, Petros A. Petrosyan · Mathematical Problems of Computer Science · 2010
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.