Geodesic
Interval edge-colorings of trees with restrictions on the edges
Proceedings of the Yerevan State University. Physical and mathematical sciences, Tome 55 (2021) no. 2, pp. 113-122.

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

An edge-coloring of a graph $G$ with consecutive integers $c_1,\ldots,c_t$ is called an interval $t$-coloring, if all colors are used, and the colors of edges incident to any 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$. In this paper, we consider the case, where there are restrictions on the edges of the tree and provide a polynomial algorithm for checking interval colorability that satisfies those restrictions.
Keywords: trees, interval $t$-coloring, interval edge-coloring, restrictions on edges, dynamic programming, bipartite matching. 
@article{UZERU_2021_55_2_a1,
     author = {A. Kh. Sahakyan and R. R. Kamalian},
     title = {Interval edge-colorings of trees with restrictions on the edges},
     journal = {Proceedings of the Yerevan State University. Physical and mathematical sciences},
     pages = {113--122},
     publisher = {mathdoc},
     volume = {55},
     number = {2},
     year = {2021},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/UZERU_2021_55_2_a1/}
}
TY  - JOUR
AU  - A. Kh. Sahakyan
AU  - R. R. Kamalian
TI  - Interval edge-colorings of trees with restrictions on the edges
JO  - Proceedings of the Yerevan State University. Physical and mathematical sciences
PY  - 2021
SP  - 113
EP  - 122
VL  - 55
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/UZERU_2021_55_2_a1/
LA  - en
ID  - UZERU_2021_55_2_a1
ER  - 
%0 Journal Article
%A A. Kh. Sahakyan
%A R. R. Kamalian
%T Interval edge-colorings of trees with restrictions on the edges
%J Proceedings of the Yerevan State University. Physical and mathematical sciences
%D 2021
%P 113-122
%V 55
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/UZERU_2021_55_2_a1/
%G en
%F UZERU_2021_55_2_a1
A. Kh. Sahakyan; R. R. Kamalian. Interval edge-colorings of trees with restrictions on the edges. Proceedings of the Yerevan State University. Physical and mathematical sciences, Tome 55 (2021) no. 2, pp. 113-122. http://geodesic.mathdoc.fr/item/UZERU_2021_55_2_a1/

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

[2] A. S. Asratian, R. R. Kamalian, “Interval colorings of edges of a multigraph”, Appl. Math., 5, Yerevan State University, 1987, 25–34 (in Russian) | MR

[3] R. R. Kamalian, Interval Colorings of Complete Bipartite Graphs and Trees, Preprint, The Computing Centre of the Academy of Sciences of Armenia, Yerevan, 1989 (in Russian)

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

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

[6] R. R. Kamalian, P. A Petrosyan, “A Note on Interval Edge-Colorings of Graphs”, Congr. Numer., 36 (2012), 13–16

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

[10] R. R. Kamalian, P. A. Petrosyan, “On Lower Bound for $W(K_{2n})$”, Mathematical Problems of Computer Science, 23 (2004), 127–129

[11] R. R. Kamalian, P. A. Petrosyan, “On Interval Edg-Colorings of Harary Graphs $H_{2n-2, 2n}$”, Mathematical Problems of Computer Science, 24 (2005), 86–88

[12] R. R. Kamalian, P. A. Petrosyan, “On Interval Colorings of Complete $k$-partite Graphs $K_n^k$”, Mathematical Problems of Computer Science, 26 (2007), 28–32

[13] P. Erdős, A. L. Rubin, H. Taylor, “Choosability in Graphs”, Proc. West Coast Conf. on Combinatorics, Graph Theory and Computing, Congress. Numer., 26, 1980, 125–157 | MR | Zbl

[14] V. G. Vizing, “Coloring the Vertices of a Graph in Prescribed Colors”, Diskret. Analiz, Novosibirsk, 29 (1976), 3–10 | MR | Zbl

[15] Y. Caro, J. Schönheim, “Generalized $1$-factorization of Trees”, Discrete Math., 33 (1981), 319–321 | DOI | MR | Zbl

[16] S. Even, A. Itai, A. Shamir, “On the Complexity of Timetable and Multicommodity Flow Problems”, SIAM J. Comput., 5:4 (1976), 691–703 | DOI | MR | Zbl

[17] R. M. Karp, “Reducibility among Combinatorial Problems”, Complexity of Computer Computations, R.E. Miller and J.W. Thatcher, Plenum Press, New York, 1972, 85–103 | Zbl

[18] S. A. Cook, “The Complexity of Theorem-proving Procedures”, Proceedings of the Third Annual ACM Symposium on Theory of Computing, 1971, 151–158 | Zbl

[19] A. S. Asratian, Investigation of Some Mathematical Model of Scheduling Theory, Doctoral Dissertation, MGU, M., 1980 (in Russian)

[20] H. W. Kuhn, “The Hungarian Method for the Assignment Problem”, Journal of the Optical Society of America A, 2:1-2 (1955), 83–97 | MR | Zbl