Граф Хватала

Граф Хватала — неорієнтований граф з 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, див. Шаблон:Harvnb), який показав, що хроматичне число графів без трикутників дорівнює O(Δ/log Δ), де Δ — найбільший степінь вершин, а O означає «O» велике. Попри це спростування, залишається цікавою задача пошуку прикладів k-колірних k-регулярних графів із малими значеннями k і великим обхватом.

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

χ (G) \leq ⌈ \frac{Δ + ω + 1}{2} ⌉ .

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

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

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