К вопросу об интервальной $\Delta$-раскраске двудольных графов

Имеется существенный класс задач, в которых составление расписания минимальной длительности сводится к правильной раскраске двудольного графа наименьшим возможным количеством цветов, а составление расписания без простоев – к интервальной раскраске двудольного графа. Исследована сложность задачи интервальной $\Delta$-раскраски двудольного мультиграфа. Построен пример $(6,3)$-бирегулярного графа, не обладающего интервальной $\Delta$-раскраской.

Статья представлена к публикации членом редколлегии: А. А. Лазарев