Граф Грёча

Граф Грёча — граф без треугольников с 11 вершинами, 20 рёбрами, хроматическим числом 4 и числом скрещиваний 5. Граф назван в честь немецкого математика Герберта Грёча и он демонстрирует необходимость предположения планарности в теореме Грёча (Grötzsch 1959), которая утверждает, что любой планарный граф без треугольников можно раскрасить в 3 цвета. Граф Грёча является членом бесконечной последовательности графов без треугольников, в которой каждый граф является мычельскианом предыдущего графа, начиная с нуль-графа. Эта последовательность графов была использована Мыцельским (Mycielski 1955), чтобы показать, что существуют графы без треугольников с произвольно большим хроматическим числом. По этой причине иногда граф Грёча называют графом Мыцельского или Мыцельского-Грёча. В отличие от других, более поздних графов в последовательности, граф Грёча является наименьшим графом без треугольников с его хроматическим числом (Chvátal 1974).

Граф Грёча
Вершин	11
Рёбер	20
Радиус	2
Диаметр	2
Обхват	4
Автоморфизмы	10 (D5)
Хроматическое число	4
Хроматический индекс	5
Свойства	гамильтонов без треугольников
Медиафайлы на Викискладе

Хеггквист (Häggkvist 1981) использовал модифицированную версию графа Грёча для опровержения гипотезы Эрдёша и Симоновича (Erdős, Simonovits 1973) о хроматическом числе графов без треугольников, имеющих большую степень. Модификация Хеггквиста заключается в замене каждой из пяти вершин степени четыре графа Грёча тремя вершинами и замене каждой из пяти вершин степени три двумя вершинами. Каждая из оставшихся вершин пятой степени заменяются четырьмя вершинами. Две вершины в этом увеличенном графе соединены ребром, если соответствующие им вершины были соединены ребром в графе Грёча. В результате получаем 10-регулярный граф без треугольников с 29 вершинами и хроматическим числом 4, что опровергает гипотезу, по которой не существует графа без треугольников с хроматическим числом 4 и n вершинами, в котором каждая вершина имеет больше чем n/3 соседей.

Граф Грёча имеет хроматический индекс, равный 5, радиус 2, обхват 4 и диаметр 2. Он является также 3-вершинно связным и 3-k-рёберно-связный граф графом. Число независимости графа равно 5 и число доминирования равно 3.