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/

[1] D.B. West, Introduction to Graph Theory, Prentice-Hall, NJ, 1996 | MR | Zbl

[2] V.G. Vizing, “The Chromatic Class of a Multigraph”, Kibernetika, 3 (1965), 29–39 (in Russian) | MR | Zbl

[3] A.S. Asratian, R.R. Kamalian, “Interval Colorings of Edges of a Multigraph”, Appl. Math., 5 (1987), 25–34 (in Russian) | MR

[4] A.S. Asratian, R.R. Kamalian, “Investigation on Interval Edge-Colorings of Graphs”, J. Combin. Theory Ser. B, 62 (1994), 34–43 | DOI | MR | Zbl

[5] R.R. Kamalian, Interval Colorings of Complete Bipartite Graphs and Trees, Preprint, Comp. Cen.of Acad. Sci. of Armenian SSR, Yer., 1989 (in Russian)

[6] H.H. Khachatrian, P.A. Petrosyan, “Interval Edge-Colorings of Complete Graphs”, Discrete Math., 339 (2016), 2249–2262 | DOI | MR | Zbl

[7] P.A. Petrosyan, “Interval Edge-Colorings of Complete Graphs and n-Dimensional Cubes”, Discrete Math., 310 (2010), 1580–1587 | DOI | MR | Zbl

[8] P.A. Petrosyan, H.H. Khachatrian, H.G. Tananyan, “Interval Edge-Colorings of Cartesian Products of Graphs I”, Discuss. Math. Graph Theory, 33 (2013), 613–632 | DOI | MR | Zbl

[9] P.A. Petrosyan, “Interval Edge Colorings of Some Products of Graphs”, Discuss. Math. Graph Theory, 31 (2011), 357–373 | DOI | MR | Zbl

[10] R.R. Kamalian, Interval Edge Colorings of Graphs, Thesis of Doctoral Dissertation, Novosibirsk, 1990 (in Russian)

[11] K. Giaro, M. Kubale, M. Malafiejski, “On the Deficiency of Bipartite Graphs”, Discrete Appl. Math., 94 (1999), 193–203 | DOI | MR | Zbl

[12] K. Giaro, M. Kubale, M. Malafiejski, “Consecutive Colorings of the Edges of General Graphs”, Discrete Math., 236 (2001), 131–143 | DOI | MR | Zbl

[13] A. Schwartz, “The Deficiency of a Regular Graph”, Discrete Math., 306 (2006), 1947–1954 | DOI | MR | Zbl

[14] M. Borowiecka-Olszewska, E. Drgas-Burchardt, “The Deficiency of all Generalized Hertz Graphs and Minimal Consecutively Non-Colourable Graphs in this Class”, Discrete Math., 339 (2016), 1892–1908 | DOI | MR | Zbl

[15] P. A. Petrosyan, H. Z. Arakelyan, “On a Generalization of Interval Edge Colorings of Graphs”, Transactions of IPIA of NAS RA. Math. Probl. of Comp. Sci., 29 (2007), 26–32

[16] P.A. Petrosyan, H.H. Khachatrian, T.K. Mamikonyan, “On Interval Edge-Colorings of Bipartite Graphs”, IEEE Computer Science and Information Technologies (CSIT), 2015, 71–76 | MR

[17] P.A. Petrosyan, H.H. Khachatrian, “On a Generalization of Interval Edge Colorings of Graphs”, 15th Workshop on Graph Theory, Colourings, Independence and Domination (Poland, Szklarska Poreba, 2013), 44

[18] S. Fiorini, “On the Chromatic Index of Outerplanar Graphs”, J. Combin. Theory Ser. B, 18 (1975), 35–38 | DOI | MR | Zbl

[19] P.A. Petrosyan, On Interval Non-Edge-Colorable Eulerian Multigraphs, 2013, arXiv: 1311.2210v2 [math.CO]

[20] M. A. Axenovich, “On Interval Colorings of Planar Graphs”, Congr. Numer., 159 (2013), 77–94 | MR

[21] K. Giaro, M. Kubale, “Compact Scheduling of Zero-One Time Operations in Multi-Stage Systems”, Discrete Appl. Math., 145 (2004), 95–103 | DOI | MR | Zbl

[22] P.A. Petrosyan, “On Interval Edge-Colorings of Outerplanar Graphs”, Ars Combinatoria, 82 (2017), 127–135

[23] D. de Werra, Ph. Solot, “Compact Cylindrical Chromatic Scheduling”, SIAM J. Discrete Math., 4 (1991), 528–534 | DOI | MR | Zbl

[24] H.J. Fleischner, D.P. Geller, F. Harary, “Outerplanar Graphs and Weak Duals”, J. Indian Math. Soc., 38 (1974), 215–219 | MR

[25] F. Harary, Graph Theory, Addison-Wesley Publishing, Reading, 1969 | MR | Zbl