Дискретная математика

Дагестанские Электронные Математические Известия, Выпуск №1 (2014)


Двудольные (6,3)-бирегулярные графы, не допускающие интервальной раскраски

УДК: 519.1

Страницы: 71 - 78


Предложенный в статье алгоритм элиминации перебора свел задачу поиска нераскрашиваемого графа к построению дерева из 11645 узлов, из которых 2485 узлов – последнего уровня; узловые графы последнего уровня образуют искомое множество {(6,3)}_6- графов M_0. Программа обнаружила среди них точно 62 нераскрашиваемых графа, а для n\le 5 выяснила раскрашиваемость всех графов из множеств – аналогов M_0 для рассматриваемых n. Тем самым получено уточнение наименьшего n, для которого существует нераскрашиваемый {(6,3)}_6-граф.


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




В содержание выпуска

Скачать полный текст