В математической области теории графов граф Мычельского или Мычельского неориентированного графа — это больший граф, образованный из него конструкцией Яна Мычельского (1955). Конструкция сохраняет свойство быть свободным от треугольников , но увеличивает хроматическое число ; применяя конструкцию повторно к исходному графу без треугольников, Мычельский показал, что существуют графы без треугольников с произвольно большим хроматическим числом.
Пусть n вершин данного графа G равны v 1 , v 2 , . . . , v n . Граф Мыцельского μ( G ) содержит сам G как подграф вместе с n +1 дополнительными вершинами: вершиной u i , соответствующей каждой вершине v i графа G , и дополнительной вершиной w . Каждая вершина u i соединена ребром с w , так что эти вершины образуют подграф в виде звезды K 1, n . Кроме того, для каждого ребра v i v j графа G граф Мыцельского включает два ребра, u i v j и v i u j .
Таким образом, если G имеет n вершин и m ребер, μ( G ) имеет 2 n +1 вершин и 3 m + n ребер.
Единственные новые треугольники в μ( G ) имеют вид v i v j u k , где v i v j v k — треугольник в G . Таким образом, если G не содержит треугольников, то и μ( G ) тоже.
Чтобы увидеть, что конструкция увеличивает хроматическое число , рассмотрим правильную k -раскраску ; то есть отображение с для смежных вершин x , y . Если бы у нас было для всех i , то мы могли бы определить правильную ( k −1)-раскраску G с помощью , когда , и в противном случае. Но это невозможно для , поэтому c должен использовать все k цветов для , и любая правильная раскраска последней вершины w должна использовать дополнительный цвет. То есть .
Повторное применение Mycielskian, начиная с графа с одним ребром, дает последовательность графов M i = μ( M i −1 ), иногда называемых графами Mycielski. Первые несколько графов в этой последовательности — это граф M 2 = K 2 с двумя вершинами, соединенными ребром, граф-цикл M 3 = C 5 и граф Грётша M 4 с 11 вершинами и 20 ребрами.
В общем случае граф M i не содержит треугольников , ( i −1)- вершинно-связен и i - хроматичен . Число вершин в M i для i ≥ 2 равно 3 × 2 i −2 − 1 (последовательность A083329 в OEIS ), а число ребер для i = 2, 3, . . . равно:
Обобщение Mycielskian, называемое конусом над графом, было введено Штибицем (1985) и далее изучено Тардифом (2001) и Лином и др. (2006). В этой конструкции граф формируется из заданного графа G путем взятия тензорного произведения G × H , где H — путь длины i с самопетлей на одном конце, а затем схлопывания в одну супервершину всех вершин, связанных с вершиной H на конце пути без петли. Сам Mycielskian может быть сформирован таким образом как μ( G ) = Δ 2 ( G ).
Хотя конструкция конуса не всегда увеличивает хроматическое число, Штибиц (1985) доказал, что это происходит при итеративном применении к K 2 . То есть, определим последовательность семейств графов, называемых обобщенными мычельскианами, как
Например, ℳ(3) — семейство нечетных циклов. Тогда каждый граф из ℳ( k ) является k -хроматическим. Доказательство использует методы топологической комбинаторики, разработанные Ласло Ловасом для вычисления хроматического числа графов Кнезера . Свойство отсутствия треугольников затем усиливается следующим образом: если применить только конструкцию конуса Δ i для i ≥ r , то полученный граф имеет нечетный обхват по крайней мере 2 r + 1, то есть он не содержит нечетных циклов длины меньше 2 r + 1. Таким образом, обобщенные мычельскианы обеспечивают простую конструкцию графов с высоким хроматическим числом и высоким нечетным обхватом.
