Граф Хватала¶

Граф Хватала — это один из классических примеров в теории графов, демонстрирующий экстремальные свойства при раскраске графов. Он представляет собой неориентированный граф, который является вершинно-4-критическим и не содержит треугольников (то есть не имеет циклов длины 3). Граф назван в честь чешско-канадского математика Вацлава Хватала, который впервые описал его в 1970 году.

¶История

В 1970 году Вацлав Хватал опубликовал статью, в которой поставил вопрос о существовании графов с большим хроматическим числом и без треугольников. До этого было известно, что для любого натурального числа \(k\) существуют графы с хроматическим числом \(k\) и без треугольников, но их конструкции были сложными и не всегда минимальными. Хватал предложил простой и наглядный пример — граф из 12 вершин, который является 4-критическим и не содержит треугольников. Этот граф вошёл в учебники как граф Хватала (Chvátal graph) и стал важным инструментом для изучения взаимосвязи между хроматическим числом, обхватом и плотностью графа.

¶Определение и свойства

Граф Хватала — это неориентированный граф с 12 вершинами и 24 рёбрами. Он является вершинно-4-критическим: его хроматическое число равно 4, но при удалении любой вершины хроматическое число полученного графа становится 3. При этом граф не содержит треугольников (обхват графа равен 4).

¶Основные числовые характеристики

Граф является регулярным степени 4 (каждая вершина соединена ровно с четырьмя другими), а также вершинно- и рёберно-транзитивным, что означает его высокую симметричность.

¶Структура графа

Граф Хватала можно описать несколькими способами. Один из наиболее наглядных — представление в виде циклического расположения вершин с определёнными соединениями.

¶Построение по окружности

Вершины графа можно расположить на окружности в порядке номеров от 0 до 11. Тогда рёбра соединяют:

• каждую вершину \(i\) с вершинами \(i+1\) и \(i+2\) (по модулю 12) — это даёт «короткие» рёбра;
• каждую вершину \(i\) с вершинами \(i+6\) и \(i+7\) (по модулю 12) — это даёт «длинные» рёбра.

Таким образом, каждая вершина имеет 4 соседа: два «ближних» (на расстоянии 1 и 2 по кругу) и два «дальних» (на расстоянии 6 и 7). В результате получается граф, не содержащий треугольников, поскольку любые два соседа вершины не соединены между собой (проверяется перебором).

¶Альтернативное описание

Граф Хватала также можно получить как граф Кэли группы \(\mathbb{Z}_{12}\) с порождающим множеством \(\{1, 2, 6, 7\}\). Это означает, что вершины соответствуют элементам циклической группы порядка 12, а рёбра соединяют элементы, разность которых (по модулю 12) равна одному из чисел 1, 2, 6 или 7.

¶Свойства и значение

¶Хроматическое число и отсутствие треугольников

Главное свойство графа Хватала — он является 4-критическим графом без треугольников. Это означает, что:

• его хроматическое число равно 4 (для раскраски вершин требуется 4 цвета);
• при удалении любой вершины хроматическое число падает до 3;
• в графе нет ни одного треугольника (цикла длины 3).

До работы Хватала было известно, что существуют графы с произвольно большим хроматическим числом и без треугольников (например, конструкции Бланша-Декарта, Мицельского и др.), но граф Хватала стал первым простым и минимальным примером для случая \(k=4\). Он показывает, что даже при отсутствии треугольников хроматическое число может быть сколь угодно большим, и минимальный такой граф для \(k=4\) имеет ровно 12 вершин.

¶Критичность

Граф является вершинно-критическим: удаление любой вершины уменьшает хроматическое число. Это свойство важно для изучения минимальных графов с заданным хроматическим числом. Граф Хватала — один из немногих известных 4-критических графов без треугольников, и он является наименьшим по числу вершин среди всех таких графов.

¶Другие свойства

• Граф является совершенным? Нет, граф Хватала не является совершенным, так как его хроматическое число (4) больше, чем размер максимальной клики (2). Это делает его примером несовершенного графа.
• Граф гамильтонов — существует цикл, проходящий через все вершины ровно один раз.
• Граф является планарным? Нет, граф Хватала не является планарным, так как содержит подразделение графа \(K_{3,3}\) или \(K_5\) (проверяется по теореме Куратовского).
• Граф является вершинно-транзитивным — группа автоморфизмов действует транзитивно на множестве вершин.

¶Применение

Граф Хватала используется в теории графов как:

• Контрпример к гипотезам о связи хроматического числа и обхвата.
• Пример для иллюстрации понятий критичности, хроматического числа и независимости.
• Учебный пример при изучении раскраски графов и экстремальных задач.
• Объект для исследования в теории Рамсея и комбинаторике.

¶Интересные факты

• Граф Хватала является одним из трёх известных 4-критических графов без треугольников с 12 вершинами (два других — граф Грёча и граф Гольднера). Все они имеют одинаковое число вершин и рёбер, но различаются структурой.
• Граф назван в честь Вацлава Хватала, который внёс значительный вклад в теорию графов, комбинаторику и оптимизацию. Он также известен работами по теории Рамсея, алгоритмам на графах и теории сложности.
• Граф Хватала является самодополнительным? Нет, его дополнение не изоморфно исходному графу.
• В 1970-х годах граф использовался для проверки гипотезы о том, что любой 4-критический граф без треугольников содержит вершину степени 3. Граф Хватала опроверг эту гипотезу, так как все его вершины имеют степень 4.

¶См. также

• Граф Грёча
• Граф Гольднера
• Хроматическое число
• Критический граф
• Обхват графа

¶Источники

• Chvátal, V. (1970). "The smallest triangle-free 4-chromatic 4-regular graph". Journal of Combinatorial Theory, 9(1), 93–94.
• Bondy, J. A., & Murty, U. S. R. (2008). Graph Theory. Springer.
• Diestel, R. (2017). Graph Theory (5th ed.). Springer.
• Weisstein, E. W. "Chvátal Graph". MathWorld – A Wolfram Web Resource.