Мычельскиан

Мычельскиан или граф Мычельского неориентированного графа — граф, созданный применением конструкции Мычельского (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 имеет 3 × 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 — граф с множеством вершин $V^{0}=\left\{v_{1}^{0},v_{2}^{0},...,v_{n}^{0}\right\}$ и множеством ребер $E^{0}$. Пусть дано целое число $m\geq 1$. Для графа G назовём m-мычельскианом граф $\mu _{m}(G)$ с множеством вершин

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

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

$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\}$

Определим $\mu _{0}(G)$ как граф, полученный добавлением универсальной вершины u. Очевидно, что мычельскиан — это просто $\mu _{1}(G)$.

Литература

• 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.
• 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. Mycielski Graph (англ.) на сайте Wolfram MathWorld.