Граф Хватала

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

Альтернативная гипотеза Брюса Рида (Bruce Reed, 1998) утверждает, что не имеющие треугольников графы с высокой степенью вершин должны иметь существенно меньшее хроматическое число по сравнению со степенью, и более обще, что графы с максимальной степенью Δ и максимальной кликой размера ω должны иметь хроматическое число

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

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

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

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

Число независимости графа равно 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.