DEFICIENCY OF OUTERPLANAR GRAPHS Hrant Khachatrian
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.
DOI: 10.46991/PYSU:A/2017.51.1.022 Physical and Mathematical Sciences, 51(1 (242) 22-28
