Граф Хватала

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

Властивості

Граф не містить трикутників — його обхват (довжина найменшого циклу) дорівнює чотирьом. Граф 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 і великим обхватом.

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

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

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

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

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

Число незалежності графа дорівнює 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 (21 квітня). — С. 93–94. — DOI:10.1016/S0021-9800(70)80057-6..
• Paul Erdős. Graph theory and probability // Canadian Journal of Mathematics. — 1959. — Т. 11 (21 квітня). — С. 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 (21 квітня). — С. 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 (21 квітня). — С. 1088–1092. — DOI:10.2307/2316101..
• Reed. ω, Δ, and χ // Journal of Graph Theory. — 1998. — Т. 27, вип. 4 (21 квітня). — С. 177–212. — DOI:10.1002/(SICI)1097-0118(199804)27:4<177::AID-JGT1>3.0.CO;2-K..

Посилання

• Weisstein, Eric W. Граф Хватала(англ.) на сайті Wolfram MathWorld.