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