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

Клетки

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

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

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

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

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

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

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

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

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

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

Примечания