График Грёча - Grötzsch graph
| График Грёча | |
|---|---|
 | |
| Названный в честь | Герберт Грётч |
| Вершины | 11 |
| Края | 20 |
| Радиус | 2 |
| Диаметр | 2 |
| Обхват | 4 |
| Автоморфизмы | 10 (D5) |
| Хроматическое число | 4 |
| Хроматический индекс | 5 |
| Толщина книги | 3 |
| Номер очереди | 2 |
| Характеристики | Гамильтониан Без треугольников |
| Таблица графиков и параметров | |
в математический поле теория графов, то График Грёча это граф без треугольников с 11 вершинами, 20 ребрами, хроматическое число 4, и номер перехода 5. Он назван в честь немецкого математика. Герберт Грётч.
Граф Грёча является членом бесконечной последовательности графов без треугольников, каждый из которых является Микельский предыдущего графика в последовательности, начиная с нулевой график; эта последовательность графиков использовалась Мыцельский (1955) показать, что существуют графы без треугольников со сколь угодно большим хроматическим числом. Поэтому граф Грёча иногда также называют графом Мицельского или графом Мицельского – Грёча. В отличие от более поздних графов в этой последовательности, граф Грёча является наименьшим графом без треугольников с его хроматическим числом (Chvátal 1974 ).
Характеристики
Полная группа автоморфизмов графа Грёча есть изоморфный к группа диэдра D5 порядка 10 группа симметрий правильный пятиугольник, включая как вращения, так и отражения.
В характеристический многочлен графа Грёча есть
Приложения
Существование графа Грёча показывает, что предположение планарности необходимо в Теорема Грёча (Грётч 1959 ) что каждый свободный от треугольников планарный граф можно раскрашивать в 3 цвета.
Хэггквист (1981) использовал модифицированную версию графа Грёча, чтобы опровергнуть гипотезу о Пол Эрдёш и Миклош Симоновиц (1973 ) от хроматического числа графов без треугольников с высокой степенью. Модификация Хэггквиста состоит в замене каждой из пяти вершин четвертой степени графа Грёча набором из трех вершин, замене каждой из пяти вершин третьей степени графа Грёча набором из двух вершин и замене оставшейся степени- пять вершин графа Грёча набором из четырех вершин. Две вершины в этом расширенном графе соединены ребром, если они соответствуют вершинам, соединенным ребром в графе Грёча. Результатом конструкции Хэггквиста является 10-регулярный граф без треугольников с 29 вершинами и хроматическим числом 4, опровергающий гипотезу о том, что не существует 4-хроматического без треугольников п-вершинный граф, в котором каждая вершина имеет более п/ 3 соседа.
Связанные графики
Граф Грёча имеет несколько общих свойств с графом Граф Клебша, а дистанционно-транзитивный граф с 16 вершинами и 40 ребрами: и граф Грёча, и граф Клебша не содержат треугольников и четыреххроматичны, и ни один из них не имеет шести вершин индуцированные пути. Этих свойств почти достаточно, чтобы охарактеризовать эти графы: граф Грёча - это индуцированный подграф графа Клебша, и каждый четырехцветный -свободный граф также является индуцированным подграфом графа Клебша, который, в свою очередь, содержит граф Грёча как индуцированный подграф (Randerath, Schiermeyer & Tewes, 2002 г. ). В Хваталь граф - еще один небольшой 4-хроматический граф без треугольников. Однако, в отличие от графа Гретча и графа Клебша, граф Хватал имеет индуцированный путь с шестью вершинами.
использованная литература
- Хватал, Вашек (1974), "Минимальность графа Mycielski", Графы и комбинаторика (Proc. Capital Conf., George Washington Univ., Вашингтон, округ Колумбия, 1973), Берлин: Конспект лекций по математике, Vol. 406, Springer-Verlag, стр. 243–246, Г-Н 0360330.
- Эрдеш, П.; Симоновиц, М. (1973), "О проблеме валентности в экстремальной теории графов", Дискретная математика, 5 (4): 323–334, Дои:10.1016 / 0012-365X (73) 90126-X, Г-Н 0342429.
- Грётч, Герберт (1959), "Zur Theorie der diskreten Gebilde, VII: Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel", Wiss. Z. Martin-Luther-U., Halle-Wittenberg, Math.-Nat. Рейхе, 8: 109–120, Г-Н 0116320.
- Хэггквист, Р. (1981), Нечетные циклы заданной длины в недвудольных графах, стр. 89–99, Г-Н 0671908.
- Мыцельски, Ян (1955), "Sur le coloriage des graphs", Коллок. Математика., 3: 161–162, Дои:10,4064 / см-3-2-161-162, Г-Н 0069494.
- Рандерат, Берт; Ширмейер, Инго; Тьюис, Мейке (2002), "Трехкратность и запрещенные подграфы. II. Полиномиальные алгоритмы", Дискретная математика, 251 (1–3): 137–153, Дои:10.1016 / S0012-365X (01) 00335-1, Г-Н 1904597.