Geodesic
Deficiency of outerplanar graphs
Proceedings of the Yerevan State University. Physical and mathematical sciences, Tome 51 (2017) no. 1, pp. 22-28

Voir la notice de l'article provenant de la source Math-Net.Ru

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. 
@article{UZERU_2017_51_1_a4,
     author = {H. H. Khachatrian},
     title = {Deficiency of outerplanar graphs},
     journal = {Proceedings of the Yerevan State University. Physical and mathematical sciences},
     pages = {22--28},
     publisher = {mathdoc},
     volume = {51},
     number = {1},
     year = {2017},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/UZERU_2017_51_1_a4/}
}
TY  - JOUR
AU  - H. H. Khachatrian
TI  - Deficiency of outerplanar graphs
JO  - Proceedings of the Yerevan State University. Physical and mathematical sciences
PY  - 2017
SP  - 22
EP  - 28
VL  - 51
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/UZERU_2017_51_1_a4/
LA  - en
ID  - UZERU_2017_51_1_a4
ER  - 
%0 Journal Article
%A H. H. Khachatrian
%T Deficiency of outerplanar graphs
%J Proceedings of the Yerevan State University. Physical and mathematical sciences
%D 2017
%P 22-28
%V 51
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/UZERU_2017_51_1_a4/
%G en
%F UZERU_2017_51_1_a4
H. H. Khachatrian. Deficiency of outerplanar graphs. Proceedings of the Yerevan State University. Physical and mathematical sciences, Tome 51 (2017) no. 1, pp. 22-28. http://geodesic.mathdoc.fr/item/UZERU_2017_51_1_a4/