A note on interval edge-colorings of graphs

الأصل · EN

An edge-coloring of a graph G with colors 1,2,,t is called an interval t-coloring if for each i∈ {1,2,,t} there is at least one edge of G colored by i, and the colors of edges incident to any vertex of G are distinct and form an interval of integers. In this paper 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 has an interval t-coloring and n≥ 2r+2, then this upper bound can be improved to 2n-5.