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

Дагестанские Электронные Математические Известия, Выпуск №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$-граф.


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




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

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