DEFICIENCY OF OUTERPLANAR GRAPHS

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.