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

граф, отриманий застосуванням побудови Мичельського

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

Побудова

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

Нехай n вершин заданого графа G — це v0, v1 і т. д. Граф Мичельського μ(G) графа G містить G в як підграф і ще n+1 вершину — по вершині ui для кожної вершини vi графа G, і ще одну вершину w. Кожна вершина ui з'єднана ребром з w так, що вершини утворюють зірку K1,n. Крім того, для кожного ребра vivj графа G граф Мичельського включає два ребра — uivj і viuj.

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

Приклад

ред.

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

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

ред.
 
Графи Мичельського M2, M3 і M4

Застосовуючи побудову мичельськіана повторно, починаючи від графа з єдиним ребром, отримаємо послідовність графів Mi = μ(Mi-1), іноді також званих графами Мичельського. Кілька перших графів у цій послідовності — це графи M2 = K2 з двома вершинами, з'єднаними ребром, цикл M3 = C5 і граф Ґрьоча з 11 вершинами і 20 ребрами.

У загальному випадку графи послідовності Mi не мають трикутників, (i-1)-вершинно зв'язні й i-хроматичні. Mi має   вершин (послідовність A083329 з Онлайн енциклопедії послідовностей цілих чисел, OEIS). Число ребер у Mi для малих i дорівнює

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

Властивості

ред.
 
Гамільтонів цикл в M4 (граф Ґрьоча)

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

ред.

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

Нехай G — граф із множиною вершин   і множиною ребер  . Нехай дано ціле число  . Для графа G назвемо m-мичельськіаном граф   зі множиною вершин

 ,

де   — це i-та копія   для  , а множина ребер

 

Визначимо   як граф, отриманий доданням універсальної вершини u. Очевидно, що мичельськіан — це просто  [1].

Примітки

ред.

Література

ред.
  • 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.