2023/03/20 by Arsen Hambardzumyan, Hambardzumyan, Arsen, Levon Muradyan +1
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · pdf · doi:10.48550/arxiv.2303.11466
openalex publication_date 2023/03/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
An edge-coloring of a graph G with colors 1,…,t is called an interval t-coloring if all colors are used and the colors of edges incident to each vertex of G are distinct and form an interval of integers. In 1990, Kamalian proved that if a graph G with at least one edge has an interval t-coloring, then t≤ 2|V(G)|-3. In 2002, Axenovich improved this upper bound for planar graphs: if a planar graph G admits an interval t-coloring, then t≤ (11)/(6)|V(G)|. In the same paper Axenovich suggested a conjecture that if a planar graph G has an interval t-coloring, then t≤ (3)/(2)|V(G)|. In this paper we confirm the conjecture by showing that if a planar graph G admits an interval t-coloring, then t≤ (3|V(G)|-4)/(2). We also prove that if an outerplanar graph G has an interval t-coloring, then t≤ |V(G)|-1. Moreover, all these upper bounds are sharp.