В 1960 году Г. Дирак выдвинул гипотезу о существовании г-связных 4-критических графов при любом r ≥ 3. В 1989 году П. Эрдёш предположил, что для всякого r ≥ 3 существуют г-однородные 4-критические графы. В настоящей статье показывается истинность этих гипотез для r = 6,8,10,12,14 и 16. Приводится список 4-критических r-однородных r-связных вершинно-транзитивных графов с числом вершин не более 47000.
展开▼