О раскрашиваемости двудольных графов специального вид

A. S. Asratyan и C. J. Casselgren доказали, что задача об интервальной реберной раскраске бирегулярного двудольного графа со степенями 6 и 3 соответственно («(6,3)-граф») NP-полна. В статье показано, что минимальная мощность $n$ вершин, при которой (6,3)-граф не допускает раскраски требуемого вида, равна 18: любой (6,3)-граф с $n<18$ допускает интервальную реберную раскраску; для каждого $n$, не меньшего, чем 18 (и кратного 3), существует (6,3)-граф с $n$ вершинами, для которого такая раскраска невозможна. Результаты находят применение в вопросах построения оптимальных расписаний учебных занятий.