Мичельськіан

Мичельськіа́н або граф Миче́льського неорієнтованого графа — граф, отриманий застосуванням побудови (Mycielski, 1955). Побудова зберігає відсутність трикутників, але збільшує хроматичне число. Мичельський показав, що застосовуючи пробудову повторно до початкового графа без трикутників, можна отримати графи без трикутників довільно великого розміру.

Побудова

Граф Ґрьоча як мичельскіан 5-циклового графа.

Нехай n вершин заданого графа G — це v₀, v₁ і т. д. Граф Мичельського μ(G) графа G містить G в як підграф і ще n+1 вершину — по вершині u_i для кожної вершини v_i графа G, і ще одну вершину w. Кожна вершина u_i з'єднана ребром з w так, що вершини утворюють зірку K_1,n. Крім того, для кожного ребра v_iv_j графа G граф Мичельського включає два ребра — u_iv_j і v_iu_j.

Так, якщо G має n вершин і m ребер, μ(G) має 2n+ 1 вершин і 3m+n ребро.

Приклад

Ілюстрація показує побудову Мичельського, застосовану до циклу з п'ятьма вершинами — v_i для 0 ≤ i ≤ 4. Отриманий мичельськіан — це граф Ґрьоча, граф з 11 вершинами і 20 ребрами. Граф Ґрьоча є найменшим графом без трикутників із хроматичним числом 4 (Chvátal, 1974).

Багаторазове повторення побудови мичельськіана

Графи Мичельського M₂, M₃ і M₄

Застосовуючи побудову мичельськіана повторно, починаючи від графа з єдиним ребром, отримаємо послідовність графів M_i = μ(M_i-1), іноді також званих графами Мичельського. Кілька перших графів у цій послідовності — це графи M₂ = K₂ з двома вершинами, з'єднаними ребром, цикл M₃ = C₅ і граф Ґрьоча з 11 вершинами і 20 ребрами.

У загальному випадку графи послідовності M_i не мають трикутників, (i-1)-вершинно зв'язні й i-хроматичні. M_i має ${\displaystyle 3\times 2^{i-2}-1}$ вершин (послідовність A083329 з Онлайн енциклопедії послідовностей цілих чисел, OEIS). Число ребер у M_i для малих i дорівнює

0, 0, 1, 5, 20, 71, 236, 755, 2360, 7271, 22196, 67355, … (послідовність A122695 з Онлайн енциклопедії послідовностей цілих чисел, OEIS).

Властивості

Гамільтонів цикл в M₄ (граф Ґрьоча)

• Якщо G має хроматичне число k, то μ(G) має хроматичне число k + 1 (Mycielski, 1955).
• Якщо G не має трикутників, то μ(G) теж не має трикутників (Mycielski, 1955).
• Узагальнюючи, якщо G має клікове число ω(G), то μ(G) має клікове число max (2, ω(G)) (Mycielski, 1955).
• Якщо G — , то таким самим є μ(G) (Došlić, 2005). Зокрема, кожен граф M_i для i ≥ 2 є фактор-критичним.
• Якщо G — гамільтонів цикл, то таким самим є μ(G) (Fisher, McKenna, Boyer, 1998).
• Якщо G має число домінування γ(G), то μ(G) має домінівне число γ(G)+1 (Fisher, McKenna, Boyer, 1998).

Конус над графами

Узагальнення мичельскіана, зване конусом над графом, увів Штибіц (Stiebitz, 1985) і згодом вивчали Тардіф (Tardif, 2001) та Лін, Ву, Лем і Гу (Lin, Wu, Lam, Gu, 2006).

Нехай G — граф із множиною вершин ${\displaystyle V^{0}=\left\{v_{1}^{0},v_{2}^{0},...,v_{n}^{0}\right\}}$ і множиною ребер ${\displaystyle E^{0}}$. Нехай дано ціле число ${\displaystyle m\geq 1}$. Для графа G назвемо m-мичельськіаном граф ${\displaystyle \mu _{m}(G)}$ зі множиною вершин

${\displaystyle V^{0}\cup V^{1}\cup V^{2}\cup ...\cup V^{m}\cup \left\{u\right\}}$,

де ${\displaystyle V^{i}=\left\{v_{j}^{i}:v_{j}^{0}\in V^{0}\right\}}$ — це i-та копія ${\displaystyle V^{0}}$ для ${\displaystyle i=1,2,...,m}$, а множина ребер

${\displaystyle E^{0}\cup \left(\bigcup _{i=0}^{m-1}\left\{v_{j}^{i}v_{j'}^{i+1}:v_{j}^{0}v_{j'}^{0}\in E^{0}\right\}\right)\cup \left\{v_{j}^{m}u:v_{j}^{m}V^{m}\right\}}$

Визначимо ${\displaystyle \mu _{0}(G)}$ як граф, отриманий доданням універсальної вершини u. Очевидно, що мичельськіан — це просто ${\displaystyle \mu _{1}(G)}$.

Примітки

1. Lin, Wu, Lam, Gu, 2006.

Література

• Václav 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)
• Tomislav Došlić. Mycielskians and matchings // Discussiones Mathematicae Graph Theory. — 2005. — Т. 25, вип. 3.
• David C. Fisher, Patricia A. McKenna, Elizabeth D. Boyer. Hamiltonicity, diameter, domination, packing, and biclique partitions of Mycielski's graphs // Discrete Applied Mathematics. — 1998. — Т. 84, вип. 1—3. — С. 93—105. — DOI:10.1016/S0166-218X(97)00126-1.
• Wensong Lin, Jianzhuan Wu, Peter Che Bor Lam, Guohua Gu. Several parameters of generalized Mycielskians // Discrete Applied Mathematics. — 2006. — Т. 154, вип. 8. — С. 1173—1182. — DOI:10.1016/j.dam.2005.11.001.
• Jan Mycielski. Sur le coloriage des graphes // Colloq. Math.. — 1955. — Т. 3. — С. 161—162. з джерела 29 жовтня 2021. Процитовано 24 березня 2022.
• M. Stiebitz. Beiträge zur Theorie der färbungskritschen Graphen. — Habilitation thesis, Technische Universität Ilmenau, 1985. Как цитировано у Тардифа (Tardif, 2001).
• C. Tardif. Fractional chromatic numbers of cones over graphs // Journal of Graph Theory. — 2001. — Т. 38, вип. 2. — С. 87—94. — DOI:10.1002/jgt.1025.
• Weisstein, Eric W. Граф Мичельського(англ.) на сайті Wolfram MathWorld.