Русская Википедия:Граф Хватала
Шаблон:Граф Граф Хватала — неориентированный граф с 12 вершинами и 24 рёбрами, открытый Вацлавом Хваталом в 1970 году.
Свойства
Граф не содержит треугольников — его обхват (длина наименьшего цикла) равен четырём. Граф 4-регулярен — каждая вершина имеет в точности четыре соседа. Хроматическое число графа равно 4 — его можно раскрасить в четыре цвета, но нельзя в три. Как обнаружил Хватал, это минимальный 4-цветный 4-регулярный граф без треугольников. Меньшим 4-цветным графом без треугольников является граф Грёча, имеющий 11 вершин, но он имеет максимальную степень 5 и не регулярен.
Граф не является вершинно-транзитивным — группа автоморфизмов имеет только одну орбиту вершин длиной 8 и одну длиной 4.
По теореме Брукса любой <math>k</math>-регулярный граф (за исключением нечётных циклов и клик) имеет хроматическое число, не превосходящее <math>k</math>. Также, благодаря Эрдёшу, с 1959 известно, что для любых <math>k</math> и <math>l</math> существуют <math>k</math>-цветные графы с обхватом <math>l</math>. Исходя из этих двух результатов и некоторых примеров, включая граф Хватала, Бранко Грюнбаум в 1970 высказал гипотезу, что для любых <math>k</math> и <math>l</math> существует <math>k</math>-цветный <math>k</math>-регулярный граф с обхватом <math>l</math>. Граф Хватала даёт решение этой гипотезы для случая <math>k</math> = <math>l</math> = 4. Гипотеза Грюнбаума была опровергнута для достаточно большого <math>k</math> ЙохансеномШаблон:Sfn, который показал, что хроматическое число графов без треугольников равно <math>O(\Delta / \log \Delta)</math>, где <math>\Delta</math> — максимальная степень вершин, а <math>O</math> означает «O» большое. Несмотря на это опровержение, остаётся интересной задача поиска примеров <math>k</math>-цветных <math>k</math>-регулярных графов с малыми значениями <math>k</math> и большим обхватом.
Альтернативная гипотеза Брюса РидаШаблон:Sfn утверждает, что не имеющие треугольников графы с высокой степенью вершин должны иметь существенно меньшее хроматическое число по сравнению со степенью, и более обще, что графы с максимальной степенью <math>\Delta</math> и максимальной кликой размера <math>\omega</math> должны иметь хроматическое число:
- <math>\chi(G)\leqslant\left\lceil\frac{\Delta+\omega+1}{2}\right\rceil</math>.
Случай <math>\omega = 2</math> этой гипотезы следует для достаточно больших <math>\Delta</math> из результата Йохансена. Граф Хватала показывает, что округление вверх в гипотезе Рида существенно, поскольку для графа Хватала <math>(\Delta + \omega + 1)/2 = 7/2</math>, что меньше хроматического числа, но становится ему равным при округлении вверх.
Граф Хватала гамильтонов и играет ключевую роль в доказательстве Фляйшнера и Сабидусси Шаблон:Sfn, что проверка, можно ли раскрасить гамильтонов граф без треугольников в три цвета, является NP-полной задачей.
Характеристический многочлен графа Хватала равен <math>(x-4) (x-1)^4 x^2 (x+1) (x+3)^2 (x^2+x-4)</math>. Многочлен Татта графа Хватала был вычислен в 2008 годуШаблон:Sfn.
Число независимости графа равно 4.
Галерея
-
Хроматическое число графа Хватала равно 4.
-
Хроматический индекс графа Хватала равен 4.
-
Граф Хватала гамильтонов.
-
Альтернативный рисунок графа Хватала.
Примечания
Литература
Ссылки
