Мычельскиан

Мычельскиан или граф Мычельского неориентированного графа — граф, созданный применением конструкции Мычельского (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 — граф с множеством вершин [math]\displaystyle{ V^0=\left\{v_1^0, v_2^0,. . ., v_n^0\right \} }[/math] и множеством ребер [math]\displaystyle{ E^0 }[/math]. Пусть дано целое число [math]\displaystyle{ m \ge 1 }[/math]. Для графа G назовём m-мычельскианом граф [math]\displaystyle{ \mu_m(G) }[/math] с множеством вершин

[math]\displaystyle{ V^0 \cup V^1 \cup V^2 \cup . . . \cup V^m \cup \left\{u\right \} }[/math],

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

[math]\displaystyle{ E^0 \cup \left(\bigcup^{m-1}_{i=0}\left\{v^i_j v^{i+1}_{j'}: v^0_j v^0_{j'} \in E^0\right\}\right) \cup \left\{ v^m_j u : v^m_j V^m \right \} }[/math]

Определим [math]\displaystyle{ \mu_0(G) }[/math] как граф, полученный добавлением универсальной вершины u. Очевидно, что мычельскиан — это просто [math]\displaystyle{ \mu_1(G) }[/math].

Литература

• 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.