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

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

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

Задача знаходження трикутників

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

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

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

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

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

Незалежна множина з ${\sqrt {n}}$ вершин у графі з n вершинами, які не мають трикутників, легко знайти — або існує вершина з більш ніж ${\sqrt {n}}$ сусідами (в цьому випадку сусіди утворюють незалежну множину), або у всіх вершин менше ніж ${\sqrt {n}}$ сусідів (у цьому випадку будь -яка найбільша незалежна множина повинна мати щонайменше ${\sqrt {n}}$ вершин). Цю межу можна злегка поліпшити — у будь-якому графі без трикутників існує незалежна множина з $\Omega ({\sqrt {n\log n}})$ вершинами, а в деяких графах без трикутників будь-яка незалежна множина має $O({\sqrt {n\log n}})$ вершин. Один із способів створити графи без трикутників, в якому всі незалежні множини малі — це triangle-free process (процес без трикутників), який створює максимальні графи без трикутників шляхом послідовного додавання випадково вибраних ребер, уникаючи створення трикутників. З великим ступенем імовірності процес утворює графи з числом незалежності $O({\sqrt {n\log n}})$. Можна знайти також знайти регулярні графи з тими ж властивостями.

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

Розфарбування графів без трикутників

Безліч досліджень за графами без трикутників зосереджені на розфарбуванні графа. Двочастковий граф (тобто, будь-який розфарбований у два кольори граф) не має трикутників, а теорема Ґрьоча стверджує, що будь —який планарний граф без трикутників може бути розфарбований у три кольори. Проте для непланарных графів без трикутників може знадобитися більше трьох кольорів.

Мичельський (Mycielski, 1955) визначив побудову, тепер звану мичельськіаном, яка утворює новий граф без трикутників з іншого графа без трикутників. Якщо граф має хроматичне число k, його мичельськіан має хроматичне число k + 1, так що дану побудову можна використати, щоб показати, що довільно велика кількість кольорів може знадобитися для розмальовки непланарного графа без трикутників. Зокрема, граф Ґрьоча, граф з 11 вершинами, утворений повторенням побудови Мичельського, є графом без трикутників, який не можна розфарбувати менше ніж чотирма кольорами, і є найменшим графом з цими властивостями. Гимбель і Томассен (Gimbel, Thomassen та , 2000) і (Nilli, 2000) показали, що число кольорів, необхідних для забарвлення будь-якого m-реберного графа без трикутників одно

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

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

Є також деякі результати щодо зв'язку розмальовки з мінімальним ступенем графів без трикутників. Андрасфай і Ердеш (Andrásfai, Erdős, vt sos, 1974) довели, що будь-який граф з n вершинами без трикутників, в якому кожна вершина має більш $2n/5$ сусідів, повинен бути двочастковим. Це найкращий можливий результат такого типу, так як 5-цикл вимагає три кольори, але має в точності $2n/5$ сусідів для кожної вершини. Натхнені цим результатом, Ердеш та Симомонович (Erdős, Simonovits, 1973) висловили гіпотезу, що будь-який граф без трикутників з n вершинами, в якому кожна вершина має щонайменше $n/3$ сусідів, може бути розфарбований тільки в три кольори. Однак Хеггквіст (Häggkvist, 1981) спростував цю гіпотезу, представивши контрприклад, в якому кожна вершина графа Ґрьоча замінена незалежною множиною спеціально підібраного розміру. Джин (Jin, 1995) показав, що будь-який граф без трикутників з n вершинами, в якому кожна вершина має більш $10n/29$ сусідів можна розфарбувати в 3 кольори. Це найкращий результат цього типу, оскільки для графа Хеггквіста потрібно чотири кольори і він має в точності $10n/29$ сусідів для кожної вершини. Нарешті, Брандт і Томасси (Brandt, Thomassé, 2006) довели, що будь-який граф без трикутників з n вершинами, в якому кожна вершина має більш ніж $n/3$ сусідів, можна розфарбувати в 4 кольори. Додаткові результати цього виду неможливі, оскільки Хайналь (Hajnal) знайшов приклади графів без трикутників з довільно великим хроматичним числом і мінімальним ступенем $(1/3-\epsilon )n$ для будь-якого $\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).