Geodesic
On interval edge-colorings of complete multipartite graphs
Proceedings of the Yerevan State University. Physical and mathematical sciences, Tome 56 (2022) no. 1, pp. 19-26.

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

A graph $G$ is called a complete $r$-partite ($r\geq 2$) graph, if its vertices can be divided into $r$ non-empty independent sets $V_1,\ldots,V_r$ in a way that each vertex in $V_i$ is adjacent to all the other vertices in $V_j$ for $1\leq i$. Let $K_{n_{1},n_{2},\ldots,n_{r}}$ denote a complete $r$-partite graph with independent sets $V_1,V_2,\ldots,V_r$ of sizes $n_{1},n_{2},\ldots,n_{r}$. An edge-coloring of a graph $G$ with colors $1,2,\ldots,t$ is called 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. In this paper we have obtained some results on the existence and construction of interval edge-colorings of complete $r$-partite graphs. Moreover, we have also derived an upper bound on the number of colors in interval colorings of complete multipartite graphs.
Keywords: edge-coloring, proper edge-coloring, interval coloring.
Mots-clés : complete multipartite graph 
@article{UZERU_2022_56_1_a2,
     author = {L. N. Muradyan},
     title = {On interval edge-colorings of complete multipartite graphs},
     journal = {Proceedings of the Yerevan State University. Physical and mathematical sciences},
     pages = {19--26},
     publisher = {mathdoc},
     volume = {56},
     number = {1},
     year = {2022},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/UZERU_2022_56_1_a2/}
}
TY  - JOUR
AU  - L. N. Muradyan
TI  - On interval edge-colorings of complete multipartite graphs
JO  - Proceedings of the Yerevan State University. Physical and mathematical sciences
PY  - 2022
SP  - 19
EP  - 26
VL  - 56
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/UZERU_2022_56_1_a2/
LA  - en
ID  - UZERU_2022_56_1_a2
ER  - 
%0 Journal Article
%A L. N. Muradyan
%T On interval edge-colorings of complete multipartite graphs
%J Proceedings of the Yerevan State University. Physical and mathematical sciences
%D 2022
%P 19-26
%V 56
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/UZERU_2022_56_1_a2/
%G en
%F UZERU_2022_56_1_a2
L. N. Muradyan. On interval edge-colorings of complete multipartite graphs. Proceedings of the Yerevan State University. Physical and mathematical sciences, Tome 56 (2022) no. 1, pp. 19-26. http://geodesic.mathdoc.fr/item/UZERU_2022_56_1_a2/

[1] A. S. Asratian, R. R. Kamalian, “Interval Colorings of Edges of a Multigraph”, Appl. Math., 5, Yerevan State University, 1987, 25–34, arXiv: (in Russian) https://arxiv.org/abs/1401.8079 | MR

[2] R. R. Kamalian, Interval Colorings of Complete Bipartite Graphs and Trees, The Computing Centre of the Academy of Sciences of Armenia, Yerevan, 1989, arXiv: (in Russian) https://arxiv.org/abs/1308.2541

[3] R. R. Kamalian, Interval Edge Colorings of Graphs, PhD Thesis, The Institute of Mathematics of the Siberian Branch of the Academy of Sciences of USSR, Novosibirsk, 1990 (in Russian)

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

[5] 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

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

[7] A. Grzesik, H. Khachatrian, “Interval Edge-colorings of $K_{1, m, n}$”, Discrete Appl. Math., 174 (2014), 140–145 | DOI | MR | Zbl

[8] Y. Feng, Q. Huang, “Consecutive Edge-coloring of the Generalized $\theta$-graphs”, Discrete Appl. Math., 155 (2007), 2321–2327 | DOI | MR | Zbl

[9] P. A. Petrosyan, “Interval Colorings of Complete Balanced Multipartite Graphs”, 2012, arXiv: https://arxiv.org/pdf/1211.5311.pdf

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

[11] A. Kh. Sahakyan, L. N. Muradyan, “Interval Edge-coloring of Even Block Graphs”, Norwegian Journal of Development of the International Science, 70 (2021), 26–30 | DOI

[12] S. V. Sevast'janov, “Interval Colorability of the Edges of a Bipartite Graph”, Metody Diskret. Analiza, 50 (1990), 61–72 (in Russian) | MR

[13] A. Kh. Sahakyan, L. N. Muradyan, “Interval Edge-coloring of Complete and Complete Bipartite Graphs with Restrictions”, World Science, 9 (2021) | DOI

[14] D. B. West, Introduction to Graph Theory, Prentice-Hall, New Jersey, 2001 | DOI | MR | Zbl

[15] H. H. Tepanyan, P. A. Petrosyan, “Interval Edge-colorings of Composition of Graphs”, Discrete Appl. Math., 127 (2017), 368–374 | DOI | MR