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/