В математической области теории графов граф Греча представляет собой граф без треугольников с 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] Граф Хватала — еще один небольшой 4-хроматический граф без треугольников. Однако, в отличие от графа Греча и графа Клебша, граф Хваталя имеет индуцированный путь с шестью вершинами.
