В математической области теории графов граф Грётша — это граф без треугольников с 11 вершинами, 20 рёбрами, хроматическим числом 4 и числом пересечений 5. Он назван в честь немецкого математика Герберта Грётша , который использовал его в качестве примера в связи со своей теоремой 1959 года о том, что планарные графы без треугольников можно раскрасить в 3 цвета. [1]
Граф Грётша является членом бесконечной последовательности графов без треугольников, каждый из которых является Мычельским предыдущего графа в последовательности, начиная с графа с одним ребром; эта последовательность графов была построена Мычельским (1955), чтобы показать, что существуют графы без треугольников с произвольно большим хроматическим числом. Поэтому граф Грётша иногда также называют графом Мычельски или графом Мычельски–Грётша. В отличие от более поздних графов в этой последовательности, граф Грётша является наименьшим графом без треугольников с его хроматическим числом. [2]
Полная группа автоморфизмов графа Грётша изоморфна диэдральной группе D 5 порядка 10, группе симметрий правильного пятиугольника , включающей как вращения, так и отражения. [3] Эти симметрии имеют три орбиты вершин: вершина степени 5 (сама по себе), ее пять соседей и ее пять не-соседей. Аналогично, есть три орбиты ребер, различающихся расстоянием от вершины степени 5.
Характеристический многочлен графа Грётша равен [3]
Хотя это не планарный граф , его можно вложить в проективную плоскость без пересечений. Это вложение имеет десять граней, все из которых являются четырехугольниками. [4]
Существование графа Грётша показывает, что предположение о планарности необходимо в теореме Грётша о том, что любой планарный граф без треугольников является 3-раскрашиваемым. [1] Он имеет нечетный обхват пять, но обхват четыре, и не имеет никакого графового гомоморфизма с графом, обхват которого равен пяти или больше, поэтому он образует пример, который отличает нечетный обхват от максимального обхвата, который может быть получен из гомоморфизма. [5]
Хеггквист (1981) использовал модифицированную версию графа Грётша, чтобы опровергнуть гипотезу Пауля Эрдёша и Миклоша Симоновича (1973) о хроматическом числе графов без треугольников с высокой степенью. Модификация Хеггквиста состоит в замене каждой из пяти вершин степени четыре графа Грётша на набор из трех вершин, замене каждой из пяти вершин степени три графа Грётша на набор из двух вершин и замене оставшейся вершины степени пять графа Грётша на набор из четырех вершин. Две вершины в этом расширенном графе соединены ребром, если они соответствуют вершинам, соединенным ребром в графе Грётша. Результатом построения Хеггквиста является 10- регулярный граф без треугольников с 29 вершинами и хроматическим числом 4, опровергающий гипотезу о том, что не существует 4-хроматического графа без треугольников, в котором каждая вершина имеет более соседей. [6] Каждый такой граф содержит граф Грётша как индуцированный подграф . [7]
Граф Грётша разделяет несколько свойств с графом Клебша , дистанционно-транзитивным графом с 16 вершинами и 40 ребрами: и граф Грётша, и граф Клебша не содержат треугольников и являются четырёхцветными, и ни один из них не имеет шестивершинных индуцированных путей . Эти свойства близки к тому, чтобы быть достаточными для характеристики этих графов: граф Грётша является индуцированным подграфом графа Клебша, и каждый четырёхцветный граф, не содержащий треугольников, также является индуцированным подграфом графа Клебша, который, в свою очередь, содержит граф Грётша в качестве индуцированного подграфа. [8] Граф Хватала является ещё одним небольшим четырёхцветным графом, не содержащим треугольников. Однако, в отличие от графа Грётша и графа Клебша, граф Хватала имеет шестивершинный индуцированный путь.
