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

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

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

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

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

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

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

Складність дерева рішень або складність запиту завдання, де запити до оракула, який запам'ятовує матриці суміжності графа, дорівнює Θ(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}$.

Див. також

• Граф Хватала

Посилання

Примітки

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.

Джерела

• 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^[en], 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).