В теории графов мыцельскианом, или графом Мыцельского, неориентированного графа называется граф, созданный применением конструкции Мыцельского (Mycielski 1955). Конструкция сохраняет отсутствие треугольников, но увеличивает хроматическое число. Мыцельский показал, что повторяя конструкцию повторно к начальному графу без треугольников, можно получить графы без треугольников произвольно большого размера.

Конструкция

Пусть 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_i = μ(M_i-1), иногда также называемых графами Мыцельского. Несколько первых графов в этой последовательности — это графы M₂ = K₂ с двумя вершинами, соединёнными ребром, цикл M₃ = C₅ и граф Грёча с 11 вершинами и 20 рёбрами.

В общем случае графы M_i в последовательности не имеют треугольников, (i-1)-вершинно связны, и i-хроматические. M_i имеет 3 × 2^i-2 — 1 вершин (последовательность A083329 в OEIS). Число рёбер в M_i для малых i равно

0, 0, 1, 5, 20, 71, 236, 755, 2360, 7271, 22196, 67355, … (последовательность A122695 в OEIS).

Свойства

• Если 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 имеет доминирующее число^[en] γ(G), то μ(G) имеет доминирующее число γ(G)+1. (Fisher, McKenna, Boyer 1998).

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

Обобщение мыцельскиана, называемое конусом над графом, было введено Штибицем (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. — В. 3. — Т. 25..
• David C. Fisher, Patricia A. McKenna, Elizabeth D. Boyer Hamiltonicity, diameter, domination, packing, and biclique partitions of Mycielski's graphs // Discrete Applied Mathematics. — 1998. — В. 1–3. — Т. 84. — С. 93–105. — 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. — В. 8. — Т. 154. — С. 1173–1182. — 10.1016/j.dam.2005.11.001.
• Jan Mycielski Sur le coloriage des graphes // Colloq. Math.. — 1955. — Т. 3. — С. 161–162..
• 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. — В. 2. — Т. 38. — С. 87–94. — 10.1002/jgt.1025.

Внешник ссылки

• Weisstein, Eric W. Mycielski Graph (англ.) на сайте Wolfram MathWorld.