Обхват (теория графов)

Обхват графа — длина наименьшего цикла, содержащегося в данном графе. Если граф не содержит циклов (то есть является ациклическим графом), его обхват по определению равен бесконечности. Например, 4-цикл (квадрат) имеет обхват 4. Квадратная решётка имеет также обхват 4, а треугольная сетка имеет обхват 3. Граф с обхватом четыре и более не имеет треугольников.

Клетки

Кубические графы (все вершины имеют степень три) с как можно меньшим обхватом $g$ известны как $g$-клетки (или как (3,$g$)-клетки). Граф Петерсена — это единственная 5-клетка (наименьший кубический граф с обхватом 5), граф Хивуда — это единственная 6-клетка, граф Макги — это единственная 7-клетка, а граф Татта — Коксетера — это единственная 8-клетка. Может существовать несколько (графов-)клеток для данного обхвата. Например, существует три неизоморфных 10-клетки, каждая с 70 вершинами — 10-клетка Балабана, граф Харриса и граф Харриса — Вонга.

• 
  Граф Петерсена имеет обхват 5
• 
  Граф Хивуда имеет обхват 6
• 
  граф Макги имеет обхват 7
• 
  Граф Татта — Коксетера (8-клетка Татта) имеет обхват 8

Обхват и раскраска графа

Для любого положительного целого $k$ существует граф $G$ с обхватом $g(G)\geq k$ и хроматическим числом $\chi (G)\geq k$. Например, граф Грёча является графом без треугольников и имеет хроматическое число 4, а многократное повторение конструкции Мыцельскиана, используемой для создания графа Грёча, образует графы без треугольников со сколь угодно большим хроматическим числом. Пал Эрдёш доказал эту теорему используя вероятностный метод.

План доказательства. Назовём циклы длиной не более $k$ короткими, а множества с $|G|/k$ и более вершин — большими. Для доказательства теоремы достаточно найти граф $G$ без коротких циклов и больших независимых множеств вершин. Тогда множества цветов в раскраске не будут большими, и, как следствие, для раскраски потребуется $k$ цветов.

Чтобы найти такой граф, будем фиксировать вероятность выбора $p$ равной $n^{\epsilon -1}$. При малых $\epsilon$ в $G$ возникает лишь малое число коротких циклов. Если теперь удалить по вершине из каждого такого цикла, полученный граф $H$ не будет иметь коротких циклов, а его число независимости будет не меньше, чем у графа $G$.

Близкие концепции

Нечётный обхват и чётный обхват графа — это длины наименьшего нечётного цикла и чётного цикла соответственно.

Окружность графа — это длина наибольшего по длине цикла, а не наименьшего.

Размышления о длине наименьшего нетривиального цикла можно рассматривать как обобщение 1-систолы или большей систолы в систолической геометрии.