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.