2010/07/10 by Rafayel R. Kamalian, R. R. Kamalian, Petros A. Petrosyan +3
Computer Science · Mathematics · #Advanced Graph Theory Research #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #cs.DM
paper · pdf · doi:10.48550/arxiv.1007.1717
4 pages, minor changes
openalex publication_date 2010/07/10 · arxiv created 2010/08/12 · arxiv updated 2010/08/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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.