DEFICIENCY OF OUTERPLANAR GRAPHS - Khachatryan, H.H. (Proceedings of the YSU A: Physical and Mathematical Sciences, 2017)
An edge-coloring of a graph G with colors $1,2,...,t$ is 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. A graph $G$ is interval colorable, if it has an interval $t$-coloring for some positive integer $t$. $def (G)$ denotes the minimum number of pendant edges that should be attached to $G$ to make it interval colorable. In this paper we study interval colorings of outerplanar graphs. In particular, we show that if $G$ is an outerplanar graph, then $def(G) ≤ (|V(G)|-2)/(og(G)-2)$, where $og(G)$ is the length of the shortest cycle with odd number of edges in $G$.
Keywords: graph theory, interval edge-coloring, deficiency, outerplanar graph