Хваталь граф - Chvátal graph

Хваталь граф
Chvatal graph.draw.svg
Названный в честьВацлав Хваталь
Вершины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.

Галерея

Рекомендации

  • Бьёрклунд, Андреас; Хусфельдт, Тор; Каски, Петтери; Койвисто, Микко (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.

внешняя ссылка