ФИЗИКО-МАТЕМАТИЧЕСКИЕ НАУКИ

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

А. М. Магомедов

Дагестанский государственный университет, г. Махачкала

Аннотация: 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$ вершинами, для которого такая раскраска невозможна. Результаты находят применение в вопросах построения оптимальных расписаний учебных занятий.

Ключевые слова: граф, двудольный, раскраска.

DOI: 10.18454/IRJ.2016.51.139