TY - JOUR
AU - Khachatryan, H.H.
PY - 2017/03/20
Y2 - 2024/07/14
TI - DEFICIENCY OF OUTERPLANAR GRAPHS
JF - Proceedings of the YSU A: Physical and Mathematical Sciences
JA - Proc. YSU A: Phys. Math. Sci.
VL - 51
IS - 1 (242)
SE - Mathematics
DO - 10.46991/PYSU:A/2017.51.1.022
UR - https://journals.ysu.am/index.php/proceedings-phys-math/article/view/vol51_no1_2017_pp022-028
SP - 22-28
AB - <p>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) \leq (|V(G)|-2)/(og(G)-2)$, where $og(G)$ is the length of the shortest cycle with odd number of edges in $G$.</p>
ER -