Граф Хватала — неорієнтований граф з 12 вершинами і 24 ребрами, який 1970 року відкрив Вацлав Хватал.
![image](https://www.wikidata.uk-ua.nina.az/image/aHR0cHM6Ly93d3cud2lraWRhdGEudWstdWEubmluYS5hei9pbWFnZS9hSFIwY0hNNkx5OTFjR3h2WVdRdWQybHJhVzFsWkdsaExtOXlaeTkzYVd0cGNHVmthV0V2WTI5dGJXOXVjeTkwYUhWdFlpODNMemRqTDBOb2RtRjBZV3hmWjNKaGNHZ3VaSEpoZHk1emRtY3ZNakl3Y0hndFEyaDJZWFJoYkY5bmNtRndhQzVrY21GM0xuTjJaeTV3Ym1jPS5wbmc=.png)
Властивості
Граф не містить трикутників — його обхват (довжина найменшого циклу) дорівнює чотирьом. Граф 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 і великим обхватом.
Альтернативна гіпотеза [en] (Брюс Рід, 1998) стверджує, що графи з високим степенем вершин, що не мають трикутників, повинні мати істотно менше хроматичне число, порівняно зі степенем, і, загальніше, що графи з найбільшим степенем Δ і найбільшою клікою розміру ω повинні мати хроматичне число
Випадок ω = 2 цієї гіпотези випливає для досить великих Δ з результату Джохансена. Граф Хватала показує, що округлення вгору в гіпотезі Ріда істотне, оскільки для графа Хватала (Δ + ω + 1)/2 = 7/2, що менше від хроматичного числа, але стає йому рівним при округленні вгору.
Граф Хватала гамільтонів і відіграє ключову роль у доведенні Фляйшнера і Сабідуссі, що перевірка, чи можна розфарбувати гамільтонів граф без трикутників у три кольори, є NP-повною задачею.
Характеристичний многочлен графа Хватала дорівнює . Многочлен Татта графа Хватала обчислив Б'єрклунд зі співавторами.
Число незалежності графа дорівнює 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. — . — DOI:.
- V. Chvátal. The smallest triangle-free 4-chromatic 4-regular graph // Journal of Combinatorial Theory. — 1970. — Т. 9, вип. 1 (19 червня). — С. 93–94. — DOI: ..
- Paul Erdős. Graph theory and probability // Canadian Journal of Mathematics. — 1959. — Т. 11 (19 червня). — С. 34–38. — DOI: ..
- Herbert Fleischner, Gert Sabidussi. 3-colorability of 4-regular Hamiltonian graphs // Journal of Graph Theory. — 2002. — Т. 42, вип. 2 (19 червня). — С. 125–140. — DOI: ..
- B. Grünbaum. A problem in graph coloring // American Mathematical Monthly. — Mathematical Association of America, 1970. — Т. 77, вип. 10 (19 червня). — С. 1088–1092. — DOI: ..
- . ω, Δ, and χ // Journal of Graph Theory. — 1998. — Т. 27, вип. 4 (19 червня). — С. 177–212. — DOI: ..
Посилання
- Weisstein, Eric W. Граф Хватала(англ.) на сайті Wolfram MathWorld.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет