2009/11/27 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.0911.5258
7 pages
arxiv created 2009/11/27 · openalex publication_date 2009/11/27 · arxiv updated 2009/12/08 · 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, the colors of edges incident to any vertex of G are distinct and form an interval of integers. In 1994 Asratian and Kamalian proved that if a connected graph G admits an interval t-coloring, then t≤ (d+1) (Δ-1) +1, and if G is also bipartite, then this upper bound can be improved to t≤ d(Δ-1) +1, where Δ is the maximum degree in G and d is the diameter of G. In this paper we show that these upper bounds can not be significantly improved.