Граф Хватала

Шаблон:Граф Граф Хватала — неориентированный граф с 12 вершинами и 24 рёбрами, открытый Вацлавом Хваталом в 1970 году.

Свойства

Граф не содержит треугольников — его обхват (длина наименьшего цикла) равен четырём. Граф 4-регулярен — каждая вершина имеет в точности четыре соседа. Хроматическое число графа равно 4 — его можно раскрасить в четыре цвета, но нельзя в три. Как обнаружил Хватал, это минимальный 4-цветный 4-регулярный граф без треугольников. Меньшим 4-цветным графом без треугольников является граф Грёча, имеющий 11 вершин, но он имеет максимальную степень 5 и не регулярен.

Граф не является вершинно-транзитивным — группа автоморфизмов имеет только одну орбиту вершин длиной 8 и одну длиной 4.

По теореме Брукса любой $k$ -регулярный граф (за исключением нечётных циклов и клик) имеет хроматическое число, не превосходящее $k$ . Также, благодаря Эрдёшу, с 1959 известно, что для любых $k$ и $l$ существуют $k$ -цветные графы с обхватом $l$ . Исходя из этих двух результатов и некоторых примеров, включая граф Хватала, Бранко Грюнбаум в 1970 высказал гипотезу, что для любых $k$ и $l$ существует $k$ -цветный $k$ -регулярный граф с обхватом $l$ . Граф Хватала даёт решение этой гипотезы для случая $k$ = $l$ = 4. Гипотеза Грюнбаума была опровергнута для достаточно большого $k$ ЙохансеномШаблон:Sfn, который показал, что хроматическое число графов без треугольников равно $O (Δ / \log Δ)$ , где $Δ$ — максимальная степень вершин, а $O$ означает «O» большое. Несмотря на это опровержение, остаётся интересной задача поиска примеров $k$ -цветных $k$ -регулярных графов с малыми значениями $k$ и большим обхватом.

Альтернативная гипотеза Брюса РидаШаблон:Sfn утверждает, что не имеющие треугольников графы с высокой степенью вершин должны иметь существенно меньшее хроматическое число по сравнению со степенью, и более обще, что графы с максимальной степенью $Δ$ и максимальной кликой размера $ω$ должны иметь хроматическое число:

χ (G) ⩽ ⌈ \frac{Δ + ω + 1}{2} ⌉

.

Случай $ω = 2$ этой гипотезы следует для достаточно больших $Δ$ из результата Йохансена. Граф Хватала показывает, что округление вверх в гипотезе Рида существенно, поскольку для графа Хватала $(Δ + ω + 1) / 2 = 7 / 2$ , что меньше хроматического числа, но становится ему равным при округлении вверх.

Граф Хватала гамильтонов и играет ключевую роль в доказательстве Фляйшнера и Сабидусси Шаблон:Sfn, что проверка, можно ли раскрасить гамильтонов граф без треугольников в три цвета, является NP-полной задачей.

Характеристический многочлен графа Хватала равен $(x - 4) (x - 1)^{4} x^{2} (x + 1) (x + 3)^{2} (x^{2} + x - 4)$ . Многочлен Татта графа Хватала был вычислен в 2008 годуШаблон:Sfn.