Граф Грёча

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

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

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

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

СсылкиПравить