Граф без треугольников

Задача нахождения треугольников — это задача определения, содержит ли граф треугольники или нет. Если граф содержит треугольник, от алгоритма часто требуют вывести три вершины, которые образуют треугольник.

Можно проверить, есть ли в графе с m рёбрами треугольники за время O(m^1.41).[1] Другой подход — найти след матрицы A³, где A — это матрица смежности графа. След равен нулю в том и только в том случае, если в графе нет треугольников. Для плотных графов более эффективен этот простой алгоритм, основанный на умножении матриц, поскольку он снижает временную сложность до O(n^2.373), где n — число вершин.

Как показали Имрих, Клавжар и Мулдер (Imrich, Klavžar, Mulder 1999), распознавание графов без треугольников эквивалентно по сложности с распознаванием медианных графов. Однако на текущий момент лучшие алгоритмы медианных графов используют в качестве подпрограммы распознавание треугольников, а не наоборот.

Сложность дерева решений или сложность запроса задачи, где запросы к оракулу, запоминающему матрицы смежности графа, равна Θ(n²). Однако для квантовых алгоритмов лучшая нижняя граница равна Ω(n), но лучший известный алгоритм имеет оценку O(n^1.29) (Belovs 2011).

Независимое множество из ${\displaystyle {\sqrt {n}}}$ вершин в графе с n вершинами, не имеющем треугольников, легко найти — либо существует вершина с более чем ${\displaystyle {\sqrt {n}}}$ соседями (в этом случае соседи образуют независимое множество), либо у всех вершин меньше чем ${\displaystyle {\sqrt {n}}}$ соседей (в этом случае любое наибольшее независимое множество должно иметь по меньшей мере ${\displaystyle {\sqrt {n}}}$ вершин)[2]. Эту границу можно слегка улучшить — в любом графе без треугольников существует независимое множество с ${\displaystyle \Omega ({\sqrt {n\log n}})}$ вершинами, а в некоторых графах без треугольников любое независимое множество имеет ${\displaystyle O({\sqrt {n\log n}})}$ вершин.[3] Один из способов создать графы без теугольников, в котором все независимые множества малы — это triangle-free process (процесс без треугольников)[4], который создаёт максимальные графы без треугольников путём последовательного добавления случайно выбранных рёбер, избегая создания треугольников. С большой степенью вероятности процесс образует графы с числом независимости ${\displaystyle O({\sqrt {n\log n}})}$. Можно найти также найти регулярные графы с теми же свойствами.[5]

Эти результаты можно также понимать как задание асимптотических границ чисел Рамсея R(3,t) в виде ${\displaystyle \Theta ({\tfrac {t^{2}}{\log t}})}$ — если рёбра полного графа с ${\displaystyle \Omega ({\tfrac {t^{2}}{\log t}})}$ вершинами раскрасить в красный и синий цвета, то либо красный граф содержит треугольник, либо в нём нет треугольников, а тогда должно существовать независимое множество размера t, соответствующее клике этого размера в синем графе.

Множество исследований по графам без треугольников сосредоточены на раскраске графа. Любой двудольный граф (то есть любой раскрашиваемый в два цвета граф) не имеет треугольников, а теорема Грёча утверждает, что любой планарный граф без треугольников может быть раскрашен в три цвета.[6] Однако для непланарных графов без треугольников может потребоваться более трёх цветов.

Мычельский (Mycielski 1955) определил конструкцию, теперь называемую мычельскианом, которая образует новый граф без треугольников из другого графа без треугольников. Если граф имеет хроматическое число k, его мычельскиан имеет хроматическое число k + 1, так что данную конструкцию можно использовать, чтобы показать, что произвольно большое число цветов может потребоваться для раскраски непланарного графа без треугольников. В частности, граф Грёча, граф с 11 вершинами, образованный повторением конструкции Мычельского, является графом без треугольников, который нельзя раскрасить меньше чем четырьмя цветами, и является наименьшим графом с этими свойствами.[7] Гимбель и Томассен (Gimbel, Thomassen & 2000) и (Nilli 2000) показали, что число цветов, необходимых для расцветки любого m-рёберного графа без треугольников, равно

${\displaystyle O\left({\frac {m^{1/3}}{(\log m)^{2/3}}}\right)}$

и существуют графы без треугольников, имеющие хроматические числа, пропорциональные этой границе.

Имеются также некоторые результаты относительно связи раскраски с минимальной степенью графов без треугольников. Андрасфай и Эрдёш (Andrásfai, Erdős, Sós 1974) доказали, что любой граф с n вершинами без треугольников, в котором каждая вершина имеет более ${\displaystyle 2n/5}$ соседей, должен быть двудольным. Это лучший возможный результат такого типа, так как 5-цикл требует три цвета, но имеет в точности ${\displaystyle 2n/5}$ соседей для каждой вершины. Воодушевлённые этим результатом, Эрдёш и Симомонович (Erdős, Simonovits 1973) высказали гипотезу, что любой граф без треугольников с n вершинами, в котором каждая вершина имеет по меньшей мере ${\displaystyle n/3}$ соседей, может быть раскрашен только в три цвета. Однако Хэггквист (Häggkvist 1981) опроверг эту гипотезу, представив контрпример, в котором каждая вершина графа Грёча заменена независимым множеством специально подобранного размера. Джин (Jin 1995) показал, что любой граф без треугольников с n вершинами, в котором каждая вершина имеет более ${\displaystyle 10n/29}$ соседей, можно раскрасить в 3 цвета. Это лучший результат этого типа, поскольку для графа Хэггквиста требуется четыре цвета и он имеет в точности ${\displaystyle 10n/29}$ соседей для каждой вершины. Наконец, Брандт и Томасси (Brandt, Thomassé 2006) доказали, что любой граф без треугольников с n вершинами, в котором любая вершина имеет более чем ${\displaystyle n/3}$ соседей, можно раскрасить в 4 цвета. Дополнительные результаты этого вида невозможны, поскольку Ха́йналь (Hajnal)[8] нашёл примеры графов без треугольников с произвольно большим хроматическим числом и минимальной степенью ${\displaystyle (1/3-\epsilon )n}$ для любого ${\displaystyle \epsilon >0}$.

Sources