Граф без трикутників

Задача знаходження трикутників — це задача визначення, чи містить граф трикутники чи ні. Якщо граф містить трикутник — від алгоритму часто вимагають знайти три вершини, які утворюють трикутник.

Можна перевірити, чи є у графі з 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, vt sos, 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}$.

Примітки

Джерела

• 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. Vt sos. 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..
• 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 комбінаторики (Proc. Capital Conf., George Washington Univ., Washington, D. C., 1973). — Springer-Verlag, 1974. — Т. 406. — С. 243-246. — (Lecture Notes in Mathematics).