On Interval Edge-Colorings of Outerplanar Graphs

Abstract

A proper edge-coloring of a graph $G$ with colors $1,\dots ,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 $\mathrm{\Delta }(G)=3$, then $G$ is interval colorable and $$w(G)=\{\begin{array}{ll}3,& \text{if }|V(G)|\text{ is even},\\ 4,& \text{if }|V(G)|\text{ is odd}.\end{array}$$
We also give a negative answer to the question of Axenovich on the outerplanar triangulations.