2013/03/05 by Petros A. Petrosyan, Petrosyan, Petros A. · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory #cs.DM #math.CO
paper · pdf · doi:10.48550/arxiv.1303.1039
9 pages, 3 figures
arxiv created 2013/03/05 · openalex publication_date 2013/03/05 · arxiv updated 2013/03/06 · 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 any vertex of G are distinct and form an interval of integers. A graph G is interval colorable if it has an interval t-coloring for some positive integer t. For an interval colorable graph G, the least value of t for which G has an interval t-coloring is denoted by w(G). A graph G is outerplanar if it can be embedded in the plane so that all its vertices lie on the same (unbounded) face. In this paper we show that if G is a 2-connected outerplanar graph with Δ(G)=3, then G is interval colorable and w(G)=\3, · if | V(G)| is even, 4, · if | V(G)| is odd.% . We also give a negative answer to the question of Axenovich on the outerplanar triangulations.