Граф Грёча

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

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

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

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

Полная группа автоморфизмов графа Грёча изоморфна диэдрической группе D₅ десятого порядка, группе симметрий правильного пятиугольника, включающей вращение и отражение.

Характеристическим многочленом графа Грёча является

${\displaystyle -(x-1)^{5}(x^{2}-x-10)(x^{2}+3x+1)^{2}.\ }$

• Граф Хватала — ещё один маленький раскрашиваемый в 4 цвета граф без треугольников.

• Chvátal. Graphs and combinatorics (Proc. Capital Conf., George Washington Univ., Washington, D.C., 1973). — Berlin: Lecture Notes in Mathematics, Vol. 406, Springer-Verlag. — С. 243–246..
• On a valence problem in extremal graph theory // Discrete Mathematics. — 1973. — Т. 5, вып. 4. — С. 323–334. — doi:10.1016/0012-365X(73)90126-X..
• Grötzsch. Zur Theorie der diskreten Gebilde, VII: Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel // Wiss. Z. Martin-Luther-U., Halle-Wittenberg, Math.-Nat. Reihe. — 1959. — Т. 8. — С. 109–120..
• Häggkvist. Odd cycles of specified length in nonbipartite graphs. — С. 89–99..
• Mycielski. Sur le coloriage des graphs // Colloq. Math.. — 1955. — Т. 3. — С. 161–162..

• Weisstein, Eric W. Grötzsch Graph (англ.) на сайте Wolfram MathWorld.