Граф Грёча
Шаблон:Граф Граф Грёча — граф без треугольников с 11 вершинами, 20 рёбрами, хроматическим числом 4 и числом скрещиваний 5. Граф назван в честь немецкого математика Шаблон:Не переведено 5 и он демонстрирует необходимость предположения планарности в теореме Грёча (Grötzsch 1959), которая утверждает, что любой планарный граф без треугольников можно раскрасить в 3 цвета. Граф Грёча является членом бесконечной последовательности графов без треугольников, в которой каждый граф является мычельскианом предыдущего графа, начиная с Шаблон:Не переведено 5. Эта последовательность графов была использована Мыцельским Шаблон:Harv, чтобы показать, что существуют графы без треугольников с произвольно большим хроматическим числом. По этой причине иногда граф Грёча называют графом Мыцельского или Мыцельского-Грёча. В отличие от других, более поздних графов в последовательности, граф Грёча является наименьшим графом без треугольников с его хроматическим числом Шаблон:Harv.
Хеггквист Шаблон:Harv использовал модифицированную версию графа Грёча для опровержения гипотезы Эрдёша и Симоновича Шаблон:Harv о хроматическом числе графов без треугольников, имеющих большую степень. Модификация Хеггквиста заключается в замене каждой из пяти вершин степени четыре графа Грёча тремя вершинами и замене каждой из пяти вершин степени три двумя вершинами. Каждая из оставшихся вершин пятой степени заменяются четырьмя вершинами. Две вершины в этом увеличенном графе соединены ребром, если соответствующие им вершины были соединены ребром в графе Грёча. В результате получаем 10-регулярный граф без треугольников с 29 вершинами и хроматическим числом 4, что опровергает гипотезу, по которой не существует графа без треугольников с хроматическим числом 4 и n вершинами, в котором каждая вершина имеет больше чем n/3 соседей.
Граф Грёча имеет хроматический индекс, равный 5, радиус 2, обхват 4 и диаметр 2. Он является также 3-вершинно связным и 3-реберно связным графом. Число независимости графа равно 5 и число доминирования равно 3.
Алгебраические свойства
Полная группа автоморфизмов графа Грёча изоморфна диэдрической группе D5 десятого порядка, группе симметрий правильного пятиугольника, включающей вращение и отражение.
Характеристическим многочленом графа Грёча является
См. также
- Граф Хватала — ещё один маленький раскрашиваемый в 4 цвета граф без треугольников.