Мицельский

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

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

Пусть n вершин данного графа G равны v ₁ , v ₂ , . . . , в _н . Граф Мицельского µ( G ) содержит сам G как подграф вместе с n +1 дополнительными вершинами: вершиной ui _, соответствующей каждой вершине vi _графа G , и дополнительной вершиной w . Каждая вершина ui _, соединена ребром с w , так что эти вершины образуют подграф в виде звезды K _{1 n} . Кроме того, для каждого ребра v _i v _j графа G граф Мисельского включает в себя два ребра u _i v _j и vi _u : _j .

Таким образом, если G имеет n вершин и m ребер, µ( G ) имеет 2 n +1 вершину и 3 m + n ребер.

Единственные новые треугольники в µ( ) имеют вид v _i v _j u _k , где vi _v j _v G _k — треугольник в G . Таким образом, если G лишена треугольников, то и µ( G ).

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

Итерированные мицельскианы

однореберного графа, дает последовательность графов M _i = µ( Mi _{−1 Повторное применение Мисельского, начиная с} ), иногда называемую графами Мицельского. Первые несколько графов в этой последовательности — это граф M ₂ = K ₂ с двумя вершинами, соединенными ребром, граф циклов M ₃ = C ₅ и граф Греча M ₄ с 11 вершинами и 20 ребрами.

В общем случае граф M _i не содержит треугольников , ( i −1) -вершинно связен и i - хроматичен . Число вершин в Mi _. для i ≥ 2 равно 3 × 2 ^{я -2} − 1 (последовательность A083329 в OEIS ), а количество ребер для i = 2, 3, . . . является:

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 ) имеет максимальное кликовое число среди 2 и ω( G ). ( Мисельский 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 ).

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

Обобщение Мицельского, называемое конусом над графом, было введено Стибицем (1985) и дополнительно изучено Тардифом (2001) и Линем и др. (2006) . В этой конструкции формируется граф $\Delta _{i}(G)$ из заданного графа G, взяв тензорное произведение G × H , где H — путь длины i с петлей на одном конце, а затем сжав в одну супервершину все вершины, связанные с вершиной H в непетлевой конец пути. Сам Мицельский может быть сформирован таким образом как µ( G ) = ∆ ₂ ( G ).

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

ℳ(2) = { K ₂ } и ℳ( k +1) = {

\Delta _{i}(G)

| G ∈ ℳ( k ), я ∈

\mathbb {N}

}.

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

Ссылки

Хватал, Вашек (1974), «Минимальность графа Мисельского», Графы и комбинаторика (Proc. Capital Conf., Университет Джорджа Вашингтона, Вашингтон, округ Колумбия, 1973) , Конспекты лекций по математике, том. 406, Springer-Verlag, стр. 243–246 .
Дошлич, Томислав (2005), «Мицельскианы и паросочетания», Дискуссии Mathematicae Graph Theory , 25 (3): 261–266, doi : 10.7151/dmgt.1279 , MR 2232992 .
Фишер, Дэвид К.; Маккенна, Патрисия А.; Бойер, Элизабет Д. (1998), «Гамильтонность, диаметр, доминирование, упаковка и бикликовые разбиения графов Мисельского», Discrete Applied Mathematics , 84 (1–3): 93–105, doi : 10.1016/S0166-218X (97 )00126-1 .
Линь, Вэнсун; Ву, Цзяньчжуань; Лам, Питер Че Бор; Гу, Гохуа (2006), «Несколько параметров обобщенных мицельскианов», Discrete Applied Mathematics , 154 (8): 1173–1182, doi : 10.1016/j.dam.2005.11.001 .
Мисельский, Ян (1955), «О раскраске графов» (PDF) , Colloq. Математика. , 3 (2): 161–162, doi : 10,4064/см-3-2-161-162 .
Штибиц, М. (1985), Вклад в теорию цветокритических графов , докторская диссертация, Технический университет Ильменау . Цитируется Тардифом (2001) .
Тардиф, К. (2001), «Дробные хроматические числа конусов над графами», Journal of Graph Theory , 38 (2): 87–94, doi : 10.1002/jgt.1025 .

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

Вайсштейн, Эрик В. «График Мицельского» . Математический мир .