RUS  ENG
Full version
JOURNALS // Proceedings of the Yerevan State University, series Physical and Mathematical Sciences // Archive

Proceedings of the YSU, Physical and Mathematical Sciences, 2017 Volume 51, Issue 1, Pages 22–28 (Mi uzeru326)

This article is cited in 3 papers

Mathematics

Deficiency of outerplanar graphs

H. H. Khachatrian

Chair of Discrete Mathematics and Theoretical Informatics YSU, Armenia

Abstract: An edge-coloring of a graph $G$ with colors $1, 2, \dots, 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) \leq (|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.

MSC: Primary 05C15; Secondary 05C10

Received: 18.11.2016
Accepted: 30.11.2016

Language: English



© Steklov Math. Inst. of RAS, 2025