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

В теории графов графом без треугольников называется неориентированный граф, в котором никакие три вершины не образуют треугольник из рёбер. Графы без треугольников можно определить также как графы с кликовым числом ≤ 2, графы с обхватом ≥ 4, графы без порождённых 3-циклов, или как локально независимые графы.

По теореме Турана граф с n вершинами, не имеющий треугольников, с максимальным числом рёбер является полным двудольным графом, в котором число вершин в каждой доле графа близки настолько, насколько возможно.

В графе с 2n вершинами, не имеющем треугольников, должно быть меньше рёбер.

Задача нахождения треугольников

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

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

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

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

Число независимости и теория Рамсея

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

Эти результаты можно также понимать как задание асимптотических границ чисел Рамсея R(3,t) в виде  — если рёбра полного графа с вершинами раскрасить в красный и синий цвета, то либо красный граф содержит треугольник, либо в нём нет треугольников, а тогда должно существовать независимое множество размера t, соответствующее клике этого размера в синем графе.

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

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

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

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

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

Ссылки

  1. Alon, Yuster, Zwick, 1994.
  2. Boppana, Halldórsson, 1992, основываясь на идее более раннего аппроксимационного алгоритма Ави Вигдерсона., p. 184.
  3. Kim, 1995.
  4. Erdős, Suen, Winkler, 1995; Bohman, 2008
  5. Alon, Ben-Shimon, Krivelevich, 2008.
  6. Grötzsch, 1959; (Thomassen 1994)).
  7. Chvátal, 1974.
  8. см. Erdős, Simonovits, 1973.
Sources
  • N. Alon, S. Ben-Shimon, M. Krivelevich. A note on regular Ramsey graphs. — 2008.
  • N. Alon, R. Yuster, U. Zwick. Proceedings of the 2nd European Symposium on Algorithms, Utrecht, The Netherlands. — 1994. С. 354–364.
  • B. Andrásfai, P. Erdős, V. T. Sós. On the connection between chromatic number, maximal clique and minimal degree of a graph // Discrete Mathematics. — 1974. Т. 8, вып. 3. С. 205–218. doi:10.1016/0012-365X(74)90133-2.
  • T. Bohman. The triangle-free process. — 2008.
  • Ravi Boppana, Magnús M. Halldórsson. Approximating maximum independent sets by excluding subgraphs // BIT. — 1992. Т. 32, вып. 2. С. 180–196. doi:10.1007/BF01994876.
  • S. Brandt, S. Thomassé. Dense triangle-free graphs are four-colorable: a solution to the Erdős-Simonovits problem. — 2006. Архивировано 4 февраля 2012 года.
  • N. Chiba, T. Nishizeki. Arboricity and subgraph listing algorithms // SIAM Journal on Computing. — 1985. Т. 14, вып. 1. С. 210–223. doi:10.1137/0214017.
  • Vašek Chvátal. Graphs and combinatorics (Proc. Capital Conf., George Washington Univ., Washington, D.C., 1973). — Springer-Verlag, 1974. — Т. 406. — С. 243–246. — (Lecture Notes in Mathematics).
  • P. Erdős, M. Simonovits. On a valence problem in extremal graph theory // Discrete Mathematics. — 1973. Т. 5, вып. 4. С. 323–334. doi:10.1016/0012-365X(73)90126-X.
  • P. Erdős, S. Suen, P. Winkler. On the size of a random maximal graph // Random Structures and Algorithms. — 1995. Т. 6, вып. 2–3. С. 309–318. doi:10.1002/rsa.3240060217.
  • John Gimbel, Carsten Thomassen. Coloring triangle-free graphs with fixed size // Discrete Mathematics. — 2000. Т. 219, вып. 1—3. С. 275–277. doi:10.1016/S0012-365X(00)00087-X.
  • H. Grötzsch. Zur Theorie der diskreten Gebilde, VII: Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel // Wiss. Z. Martin-Luther-U., Halle-Wittenberg, Math.-Nat. Reihe. — 1959. Т. 8. С. 109–120.
  • R. Häggkvist. Graph Theory (Cambridge, 1981). — 1981. С. 89–99.
  • Wilfried Imrich, Sandi Klavžar, Henry Martyn. Median graphs and triangle-free graphs // SIAM Journal on Discrete Mathematics. — 1999. Т. 12, вып. 1. С. 111–118. doi:10.1137/S0895480197323494.
  • A. Itai, M. Rodeh. Finding a minimum circuit in a graph // SIAM Journal on Computing. — 1978. Т. 7, вып. 4. С. 413–423. doi:10.1137/0207033.
  • G. Jin. Triangle-free four-chromatic graphs // Discrete Mathematics. — 1995. Т. 145, вып. 1—3. С. 151–170. doi:10.1016/0012-365X(94)00063-O.
  • J. H. Kim. The Ramsey number has order of magnitude  // Random Structures and Algorithms. — 1995. Т. 7, вып. 3. С. 173–207.
  • Frederic Magniez, Miklos Santha, Mario Szegedy. Quantum Algorithms for the Triangle Problem. — 2003.
  • J. Mycielski. Sur le coloriage des graphes // Colloq. Math.. — 1955. Т. 3. С. 161–162.
  • A. Nilli. Triangle-free graphs with large chromatic numbers // Discrete Mathematics. — 2000. Т. 211, вып. 1–3. С. 261–262. doi:10.1016/S0012-365X(99)00109-0.
  • J. B. Shearer. Note on the independence number of triangle-free graphs // Discrete Mathematics. — 1983. Т. 46, вып. 1. С. 83–87. doi:10.1016/0012-365X(83)90273-X.
  • C. Thomassen. Grötzsch's 3-color theorem // Journal of Combinatorial Theory, Серия B. — 1994. Т. 62, вып. 2. С. 268–279. doi:10.1006/jctb.1994.1069.
  • Aleksandrs Belovs. Span Programs for Functions with Constant-Sized 1-certificates. — 2011.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.