Граф Хватала

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

Граф Хватала
Назван в честь	Вацлав Хватал
Вершин	12
Рёбер	24
Радиус	2
Диаметр	2
Обхват	4
Автоморфизмы	8 (D4)
Хроматическое число	4
Хроматический индекс	4
Свойства	регулярный гамильтонов эйлеров без треугольников
Медиафайлы на Викискладе

Свойства

Граф не содержит треугольников — его обхват (длина наименьшего цикла) равен четырём. Граф 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$ Йохансеном, который показал, что хроматическое число графов без треугольников равно $O(\Delta /\log \Delta )$, где $\Delta$ — максимальная степень вершин, а $O$ означает «O» большое. Несмотря на это опровержение, остаётся интересной задача поиска примеров $k$-цветных $k$-регулярных графов с малыми значениями $k$ и большим обхватом.

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

$\chi (G)\leqslant \left\lceil {\frac {\Delta +\omega +1}{2}}\right\rceil$.

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

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

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

Число независимости графа равно 4.

Галерея

• 
  Хроматическое число графа Хватала равно 4.
• 
  Хроматический индекс графа Хватала равен 4.
• 
  Граф Хватала гамильтонов.
• 
  Альтернативный рисунок графа Хватала.

Литература

• Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko Koivisto. FOCS '08: Proceedings of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science. — Washington, DC, USA: IEEE Computer Society, 2008. — С. 677–686. — ISBN 978-0-7695-3436-7. — doi:10.1109/FOCS.2008.40..
• V. Chvátal. The smallest triangle-free 4-chromatic 4-regular graph // Journal of Combinatorial Theory. — 1970. — Т. 9, вып. 1. — С. 93–94. — doi:10.1016/S0021-9800(70)80057-6..
• Paul Erdős. Graph theory and probability // Canadian Journal of Mathematics. — 1959. — Т. 11. — С. 34–38. — doi:10.4153/CJM-1959-003-9..
• Herbert Fleischner, Gert Sabidussi. 3-colorability of 4-regular Hamiltonian graphs // Journal of Graph Theory. — 2002. — Т. 42, вып. 2. — С. 125–140. — doi:10.1002/jgt.10079..
• B. Grünbaum. A problem in graph coloring // American Mathematical Monthly. — Mathematical Association of America, 1970. — Т. 77, вып. 10. — С. 1088–1092. — doi:10.2307/2316101. — ..
• Reed. ω, Δ, and χ // Journal of Graph Theory. — 1998. — Т. 27, вып. 4. — С. 177–212. — doi:10.1002/(SICI)1097-0118(199804)27:4<177::AID-JGT1>3.0.CO;2-K..

Ссылки

• Weisstein, Eric W. Chvátal Graph (англ.) на сайте Wolfram MathWorld.