Граф Хватала

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

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

Свойства

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

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

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

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

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

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

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

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

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

Галерея

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

Примечания

1. Reed, 1998.
2. Fleischner, Sabidussi, 2002.
3. Björklund, 2008.

Литература

• 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. — JSTOR 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.