WikiDer > Микельский

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

строительство

Конструкция Мицельского применительно к 5-график цикла, производя График Грёча с 11 вершинами и 20 ребрами наименьший 4-хроматический граф без треугольников (Chvátal 1974).

Пусть п вершины данного графа г быть v₁, v₂, . . . , v_п. Граф Микельского μ (г) содержит г сам как подграф вместе с п+1 дополнительные вершины: вершина ты_я соответствующая каждой вершине v_я из г, и лишняя вершина ш. Каждая вершина ты_я соединяется ребром с ш, так что эти вершины образуют подграф в виде звезды K_1,п. Кроме того, для каждого ребра v_яv_j из г, граф Мицельского содержит два ребра, ты_яv_j и v_яты_j.

Таким образом, если г имеет п вершины и м ребра, μ (г) имеет 2п+1 вершина и 3м+п края.

Единственные новые треугольники в μ (г) имеют вид v_яv_jты_k, где v_яv_jv_k это треугольник в г. Таким образом, если г не содержит треугольников, поэтому μ (г).

Чтобы увидеть, что конструкция увеличивает хроматическое число ${displaystyle chi (G) = k}$, рассмотрите надлежащий k-крашивание ${displaystyle mu (G) {-} {w}}$; то есть отображение ${displaystyle c: {v_ {1}, ldots, v_ {n}, u_ {1}, ldots, u_ {n}} o {1,2, ldots, k}}$ с ${displaystyle c (x) eq c (y)}$ для смежных вершин Икс,у. Если бы у нас было ${displaystyle c (u_ {i}) подмножество {1,2, ldots, k {-} 1}}$ для всех я, то мы могли бы определить собственное (k−1) -раскрашивание г от ${displaystyle c '! (v_ {i}) = c (u_ {i})}$ когда ${displaystyle c (v_ {i}) = k}$, и ${displaystyle c '! (v_ {i}) = c (v_ {i})}$ иначе. Но это невозможно для ${displaystyle chi (G) = k}$, так c должен использовать все k цвета для ${displaystyle {u_ {1}, ldots, u_ {n}}}$, и любая правильная раскраска последней вершины ш необходимо использовать дополнительный цвет. Это, ${displaystyle chi (mu (G)) = k {+} 1}$.

Итерированные Mycielskians

M₂, M₃ и M₄ Графики Микельского

Многократное применение микельского, начиная с однореберного графа, дает последовательность графов M_я = μ (M_я−1), иногда называемые графами Мыцельского. Первые несколько графиков в этой последовательности - это график M₂ = K₂ с двумя вершинами, соединенными ребром, график цикла M₃ = C₅, а График Грёча M₄ с 11 вершинами и 20 ребрами.

В общем график M_я является без треугольников, (я−1)-вершинно-связанный, и я-хроматический. Количество вершин в M_я за я ≥ 2 равно 3 × 2^я−2 - 1 (последовательность A083329 в OEIS), а количество ребер для я = 2, 3,. . . является:

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

Характеристики

Гамильтонов цикл в M₄ (График Грёча)

• Если г имеет хроматическое число k, то μ (г) имеет хроматическое число k + 1 (Мыцельский 1955).
• Если г является без треугольников, то и μ (г) (Мыцельский 1955).
• В более общем смысле, если г имеет номер клики ω (г), то μ (г) имеет кликовое число max (2, ω (г)).(Мыцельский 1955).
• Если г это факторно-критический граф, то и μ (г) (Дошлич 2005). В частности, каждый граф M_я за я ≥ 2 является фактор-критичным.
• Если г имеет Гамильтонов цикл, то и μ (г) (Фишер, МакКенна и Бойер, 1998 г.).
• Если г имеет число господства γ (г), то μ (г) имеет число доминирования γ (г)+1. (Фишер, Маккенна и Бойер, 1998 г.).

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

Обобщенный микельский, сформированный как конус над 5-циклом, Δ₃(C₅) = Δ₃(Δ₂(K₂)).

Обобщение микельского, названное конусом над графом, было введено Стибиц (1985) и далее изучен Тардиф (2001) и Lin et al. (2006). В этой конструкции формируется граф Δ_я(г) из заданного графа г взяв тензорное произведение графов г × ЧАС, где ЧАС это путь длины я с петлей на одном конце, а затем коллапсирует в одну супервершину все вершины, связанные с вершиной ЧАС на конце пути без петли. Сам микельский может быть образован таким образом как μ (г) = Δ₂(г).

Хотя конструкция диффузора не всегда увеличивает хроматическое число, Стибиц (1985) доказал, что это так при итеративном применении к K₂. Таким образом, определите последовательность семейств графов, называемых обобщенными микельскими графами, как

ℳ (2) = {K₂} и ℳ (k+1) = {Δ_я(г) | г ∈ ℳ (k), i ∈ ℕ}.

Например, ℳ (3) - это семейство нечетных циклов. Тогда каждый граф из ℳ (k) является k-хроматический. Доказательство использует методы топологическая комбинаторика разработан Ласло Ловас для вычисления хроматического числа Графы КнезераСвойство отсутствия треугольников усиливается следующим образом: если применить только конструкцию конуса ∆_я за я ≥ р, то полученный граф имеет странный обхват минимум 2р + 1, то есть не содержит нечетных циклов длины меньше 2р + 1. Таким образом, обобщенные микельскианцы обеспечивают простое построение графов с большим хроматическим числом и большим нечетным обхватом.

использованная литература

• Хватал, Вашек (1974), "Минимальность графа Mycielski", Графы и комбинаторика (Proc. Capital Conf., George Washington Univ., Вашингтон, округ Колумбия, 1973), Конспект лекций по математике, 406, Springer-Verlag, стр. 243–246..
• Дошлич, Томислав (2005), «Мыцельские и матчи», Обсуждения Математическая теория графов, 25 (3): 261–266, Дои:10.7151 / dmgt.1279, Г-Н 2232992.
• Фишер, Дэвид С .; McKenna, Patricia A .; Бойер, Элизабет Д. (1998), "Гамильтоничность, диаметр, доминирование, упаковка и бикликовые разбиения графов Микельского", Дискретная прикладная математика, 84 (1–3): 93–105, Дои:10.1016 / S0166-218X (97) 00126-1.
• Линь, Вэнсонг; Ву, Цзяньчжуань; Лам, Питер Че Бор; Гу, Гохуа (2006), "Несколько параметров обобщенных микельских", Дискретная прикладная математика, 154 (8): 1173–1182, Дои:10.1016 / j.dam.2005.11.001.
• Мыцельски, Ян (1955), "Sur le coloriage des graphes" (PDF), Коллок. Математика., 3: 161–162.
• Стибиц, М. (1985), Beiträge zur Theorie der färbungskritschen Graphen, Докторская диссертация, Technische Universität Ilmenau. Как цитирует Тардиф (2001).
• Тардиф, К. (2001), "Дробное хроматическое число конусов над графами", Журнал теории графов, 38 (2): 87–94, Дои:10.1002 / jgt.1025.

внешняя ссылка

• Вайсштейн, Эрик В. "Граф Мыцельского". MathWorld.