Том 10, серия 1, номер 3, 2003 г., Стр. 12-22
УДК 519.17
А. А. Добрынин, Л. С. Мельников, А. В. Пяткин
Критические графы Эрдёша и Дирака четной степени
Аннотация:
В 1960 году Г. Дирак выдвинул гипотезу о существовании$r$ -связных 4-критических графов при любом$r\geqslant 3$ . В 1989 году П. Эрдёш предположил, что для всякого$r\geqslant 3$ существуют$r$ -однородные 4-критические графы. В настоящей статье показывается истинность этих гипотез для$r=6$ , 8, 10, 12, 14 и 16. Приводится список 4-критических$r$ -однородных$r$ -связных вершинно-транзитивных графов с числом вершин не более 47000.
Добрынин А. А. 1
Мельников Л. С. 1
Пяткин А. В. 1
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
е-mail: dobr@math.nsc.ru, omeln@math.nsc.ru, artem@math.nsc.ru
Статья поступила 14 мая 2003 г.
