Interval edge-colorings of trees with restrictions on the edges

Раскраска ребер графа $G$ последовательными целыми числами $c_1,\ldots,c_t$ называется интервальной $t$-раскраской, если используются все цвета и цвета ребер, инцидентных любой вершине графа $G$, различны и образуют интервал целых чисел. Граф $G$ является интервально раскрашиваемым, если он имеет интервальную $t$-раскраску для некоторого натурального $t$. В работе рассматривается задача существования интервальной раскраски дерева с заданными ограничениями на его ребрах. Представлен полиномиальный алгоритм проверки существования интервальной раскраски, удовлетворяющей этим ограничениям.