Граф Хватала

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

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

СвойстваПравить

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

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

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

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

$\mathrm{\chi <!--\; \chi \; -->}(G)⩽<!--\; ⩽\; -->\lceil \frac{\mathrm{\Delta <!--\; \Delta \; -->}+\mathrm{\omega <!--\; \omega \; -->}+1}{2}\rceil$$\chi (G)\leqslant \left\lceil {\frac {\Delta +\omega +1}{2}}\right\rceil$ .

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

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

Характеристический многочлен графа Хватала равен $(x-<!--\; -\; -->4)(x-<!--\; -\; -->1{)}^4{x}^2(x+1)(x+3{)}^2(x^2+x-<!--\; -\; -->4)$$(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. — 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.