Граф Хватала

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

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

Свойства

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

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

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

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

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

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

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

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

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

[_a4fc6f79f2096120-1] 1,0 ^1,1 Reed, 1998.

[_8d4089a26eb249dd-2] Fleischner, Sabidussi, 2002.

[_809f60359639f1dc-3] Björklund, 2008.

[1]

[2]

[3]