Хваталь граф - Chvátal graph
| Хваталь граф | |
|---|---|
 | |
| Названный в честь | Вацлав Хваталь |
| Вершины | 12 |
| Края | 24 |
| Радиус | 2 |
| Диаметр | 2 |
| Обхват | 4 |
| Автоморфизмы | 8 (D4 ) |
| Хроматическое число | 4 |
| Хроматический индекс | 4 |
| Толщина книги | 3 |
| Номер очереди | 2 |
| Характеристики | Обычный Гамильтониан Без треугольников Эйлеров |
| Таблица графиков и параметров | |
в математический поле теория графов, то Хваталь граф является неориентированный граф с 12 вершинами и 24 ребрами, обнаруженными Вацлав Хваталь (1970 ).
это без треугольников: это обхват (длина его кратчайшего цикла) - четыре. Это 4-обычный: у каждой вершины ровно четыре соседа. И это хроматическое число равно 4: его можно раскрасить четырьмя цветами, но не только тремя. Это, как отмечает Хватал, наименьший возможный 4-хроматический 4-регулярный граф без треугольников; единственный меньший 4-хроматический граф без треугольников - это График Грёча, который имеет 11 вершин, но имеет максимальную степень 5 и не является правильным.
Этот график не вершинно-транзитивный: группа автоморфизмов имеет одну орбиту на вершинах размера 8 и одну орбиту размера 4.
К Теорема Брукса, каждый k-регулярный граф (кроме нечетных циклов и клик) имеет хроматическое число не более k. Это было также известно с Эрдёш (1959) что для каждого k и л существуют k-хроматические графики с обхватом л. В связи с этими двумя результатами и несколькими примерами, включая граф Хватала,Бранко Грюнбаум (1970 ) предположил, что для каждого k и л существуют k-хроматический k-регулярные графики с обхватом л. Граф Хватала решает случай k = л = 4 этой гипотезы. Гипотеза Грюнбаума была опровергнута для достаточно больших k Йоханссена (см. Рид 1998 ), который показал, что хроматическое число графа без треугольников равно O (Δ / log Δ), где Δ - максимальная степень вершины, а O вводит нотация большой O. Однако, несмотря на это опровержение, по-прежнему интересно найти такие примеры, как граф Хватала для больших обхватов. k-хроматический k-регулярные графики для малых значений k.
Альтернативная гипотеза Брюс Рид (1998 ) утверждает, что графы с высокой степенью без треугольников должны иметь значительно меньшее хроматическое число, чем их степень, и в более общем плане, что граф с максимальной степенью Δ и максимальная клика размер ω должен иметь хроматический номер
Случай ω = 2 этой гипотезы следует при достаточно большом Δ из результата Йоханссена. График Хватала показывает, что округление в гипотезе Рида необходимо, потому что для графа Хватала (Δ + ω + 1) / 2 = 7/2, число, которое меньше хроматического числа, но становится равным хроматическому числу. число при округлении в большую сторону.
Граф Chvátal Гамильтониан, и играет ключевую роль в доказательстве Флейшнер и Сабидусси (2002) что это НП-полный чтобы определить, является ли гамильтонов граф без треугольников 3-раскрашиваемым.
В характеристический многочлен графа Хватал . В Полином Тутте графа Хватал был вычислен Björklund et al. (2008).
В число независимости этого графика равно 4.
Галерея
В хроматическое число графа Хватала равно 4.
В хроматический индекс графа Хватала равно 4.
Граф Chvátal Гамильтониан.
Альтернативный рисунок графа Chvátal.
Рекомендации
- Бьёрклунд, Андреас; Хусфельдт, Тор; Каски, Петтери; Койвисто, Микко (2008), "Вычисление полинома Тутте за вершинно-экспоненциальное время", FOCS '08: Материалы 49-го ежегодного симпозиума IEEE 2008 г. по основам компьютерных наук, Вашингтон, округ Колумбия, США: Компьютерное общество IEEE, стр. 677–686, arXiv:0711.2585, Дои:10.1109 / FOCS.2008.40, ISBN 978-0-7695-3436-7.
- Хватал, В. (1970), "Наименьший 4-хроматический 4-регулярный граф без треугольников", Журнал комбинаторной теории, 9 (1): 93–94, Дои:10.1016 / S0021-9800 (70) 80057-6.
- Эрдеш, Пол (1959), «Теория графов и вероятность», Канадский математический журнал, 11: 34–38, Дои:10.4153 / CJM-1959-003-9.
- Флейшнер, Герберт; Сабидусси, Герт (2002), "3-раскрашиваемость 4-регулярных гамильтоновых графов", Журнал теории графов, 42 (2): 125–140, Дои:10.1002 / jgt.10079.
- Грюнбаум, Б. (1970), «Задача раскраски графа», Американский математический ежемесячный журнал, Математическая ассоциация Америки, 77 (10): 1088–1092, Дои:10.2307/2316101, JSTOR 2316101.
- Рид, Б.А. (1998), «ω, Δ и χ», Журнал теории графов, 27 (4): 177–212, Дои:10.1002 / (SICI) 1097-0118 (199804) 27: 4 <177 :: AID-JGT1> 3.0.CO; 2-K.