On Interval Edge-Colorings of Outerplanar Graphs

Abstract

A proper edge-coloring of a graph \(G\) with colors \(1, \ldots, t\) is called an interval \(t\)-coloring if the colors of edges incident to any vertex of \(G\) 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 \(\Delta(G) = 3\), then \(G\) is interval colorable and \[ w(G) = \begin{cases} 3, & \text{if } |V(G)| \text{ is even}, \\ 4, & \text{if } |V(G)| \text{ is odd}. \end{cases} \]
We also give a negative answer to the question of Axenovich on the outerplanar triangulations.