Граф Грёча — граф без треугольников с 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-реберно связным графом. Число независимости графа равно 5 и число доминирования равно 3.
Алгебраические свойства
Полная группа автоморфизмов графа Грёча изоморфна диэдрической группе D5 десятого порядка, группе симметрий правильного пятиугольника, включающей вращение и отражение.
Характеристическим многочленом графа Грёча является
См. также
- Граф Хватала — ещё один маленький раскрашиваемый в 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..
Ссылки
