Раскраска графика

Правильная раскраска вершин графа Петерсена в 3 цвета, минимально возможное количество.

В теория графов, раскраска графов является частным случаем разметки графов ; это присвоение меток, традиционно называемых «цветами», элементам графа с учетом установленных ограничений. В своей простейшей форме это способ раскраски вершин графа таким образом, чтобы никакие две соседние вершины не были одного цвета; это называется раскраской вершины . Точно так же раскраска ребер назначает цвет каждому ребру так, чтобы никакие два соседних ребра не были одного цвета, а раскраска граней плоского графа назначает цвет каждой грани или области, чтобы никакие две грани, имеющие общую границу, не имели одинаковый цвет.

Раскраска вершин обычно используется для задач введения раскраски графов, поскольку другие задачи раскраски могут быть преобразованы в экземпляр раскраски вершин. Например, окраска ребер графа - это просто окраска вершин его линейного графа, а окраска граней плоского графа - это просто окраска вершин его двойственного. Однако проблемы не вершинной раскраски часто формулируются и изучаются как есть. Отчасти это педагогический, а отчасти потому, что некоторые задачи лучше всего изучать в не вершинной форме, как в случае раскраски ребер.

Соглашение об использовании цветов происходит от раскрашивания стран на карте, где каждое лицо буквально окрашено. Это было обобщено для раскраски граней графа , вложенного в плоскость. Планарной двойственностью он стал раскрашиванием вершин и в таком виде обобщается на все графы. В математических и компьютерных представлениях типично использовать первые несколько положительных или неотрицательных целых чисел в качестве цветов. В общем, в качестве в «цветового набора» можно использовать любой конечный набор. Характер проблемы окраски зависит от количества цветов, а не от того, какие они есть.

Раскраска графов имеет множество практических приложений, а также решает теоретические задачи. Помимо классических типов задач установлены ограничения также могут быть на графике, или на способ назначения цвета, или на сам цвет. Он даже приобрел популярность среди широкой публики в форме популярной головоломки с числами Судоку. Раскраска графиков - все еще очень активная область исследований.

Примечание: многие термины, используемые в этой статье, в Глоссарии теории графов.

• 1 История
• 2 Определение и терминология
  • 2.1 Раскраска вершин
  • 2.2 Хроматический многочлен
  • 2.3 Раскраска ребер
  • 2.4 Полная раскраска
  • 2.5 Непомеченная раскраска
• 3 Свойства
  • 3.1 Верхние границы хроматического числа
  • 3.2 Нижние границы хроматического числа
  • 3.3 Графики с высоким хроматическим числом
  • 3.4 Границы хроматического индекса
  • 3.5 Другие свойства
  • 3.6 Открытые задачи
• 4 Алгоритмы
  • 4.1 Полиномиальное время
  • 4.2 Точные алгоритмы
  • 4.3 Сокращение
  • 4.4 Жадная раскраска
  • 4.5 Параллельные и распределенные алгоритмы
  • 4.6 Децентрализованные алгоритмы
  • 4.7 Вычислительная сложность
• 5 Приложения
  • 5.1 Планирование
  • 5.2 Размещение регистров
  • 5.3 Другие приложения
• 6 Другое раскраски
  • 6.1 Теория Рамсея
  • 6.2 Другие раскраски
• 7 См. также
• 8 Примечания
• 9 Ссылки
• 10 Внешние ссылки

Первые результаты Процесс раскраски графов имеет дело почти исключительно с планарными графами в форме раскраски карт. Пытаясь раскрасить карту графств Англии, Фрэнсис Гатри постулировал четырехцветную гипотезу, отметив, что четырех цветов достаточно для раскраски карты, так что ни один регион не имеет общей границы. получил такой же цвет. Брат Гатри передал этот вопрос своему учителю математики Августу де Моргану в Университетском колледже, который заключил его в письме Уильяму Гамильтону в 1852 году. Артур Кейли поднял эту проблему на собрании Лондонского математического общества в 1879 году. В том же году Альфред Кемпе опубликовал статью, в которой утверждено, что установил результат и десятилетие проблема четырех цветов считалась решенной. За свои достижения Кемпе был избранным членом Королевского общества, а затем президентом Лондонского математического общества.

В 1890 году Хивуд указал, что аргумент Кемпе неверен.. Однако в статье он доказал теорему о пяти цветах, заявив, что каждая планарная карта может быть раскрашена не более чем в пяти цветах, используя идеи Кемпе. В следующем столетии было разработано огромное количество работ и теорий, чтобы уменьшить количество цветов до четырех, пока теорема о четырех цветах не была окончательно доказана в 1976 году Кеннетом Аппелем и Вольфгангом Хакеном <273.>. Доказательство восходит к идеям Хивуда и Кемпе и в степени игнорирует промежуточные разработки. Доказательство теоремы о четырех цветах также заслуживает внимания как первое крупное компьютерное доказательство.

В 1912 году Джордж Дэвид Биркгоф представил хроматический многочлен для изучения проблем раскраски, который был обобщен на многочлен Тутте с помощью Тутт важные структуры в теории алгебраических графов. Последовательность действий в начале 20 века.

В 1960 году Клод Берже сформулировал другую гипотезу о раскраске графов, сильную гипотезу об идеальном графе, мотивированную теоретико-информационную концепцию, названной представленной концепцией графа. Автор Шеннон. Гипотеза оставалась неразрешенной в течение 40 лет, пока не была установлена ​​в виде знаменитой сильной теоремы об идеальном графе Чудновским, Робертсоном, Сеймуром, и Томас в 2002 году.

Раскраска графов изучалась как алгоритмическая проблема с начала 1970-х годов: проблема хроматических чисел - одна из 21 NP-полных задач Карпа с 1972 года, и примерно в то же время были разработаны различные алгоритмы экспоненциального времени, основанные на отслеживании с возвратом и на повторении удаления-сокращения Зыкова (1949). Одно из основных применений раскраски графов, распределение регистров в компиляторах, было введено в 1981 году.

Этот граф можно раскрасить в 3 цвета 12 способами.

Раскраска вершин

При использовании без каких-либо проверок раскраска графа почти всегда является правильной раскраской вершин, а именно разметкой вершин графа такими цветами, что никакие две вершины не имеют общих общих края имеют одинаковый цвет. Вершина с петлей (то есть непосредственно с собой) никогда не может быть правильно окрашена, понятно, что графы в этом контексте не имеют петель.

Терминология использования цветов для меток вершин восходит к раскраске карты. Такие метки, как красный и синий, используются только тогда, когда количество цветов невелико, и обычно подразумевается, что метки нарисованы из целых чисел {1, 2, 3,...}.

Раскраска с использованием не более k цветов называется (собственно) k-раскраской . Наименьшее количество цветов, необходимое для раскраски графа G, называется его хроматическим числом и часто обозначается χ (G). Иногда используется γ (G), поскольку χ (G) также используется для обозначения эйлеровой характеристики графа. Графическим может быть присвоена (правильная) k-раскраска, является k-раскрашиваемым, и он является k-хроматическим, если его хроматическое число равно k. Подмножество вершин, которому назначен один и тот же цвет, называется классом цвета, каждый такой класс образует независимый набор. Таким образом, k-раскраска - это то же самое, что разбиение набора вершин на независимых множеств, термины k-partite и k-colorable имеют одинаковое значение.

Хроматический многочлен

Все неизоморфные графы с 3-мя вершинами и их хроматические многочлены. Пустой граф E 3 (красный) допускает 1-раскраску; другие не допускают такой окраски. Зеленый граф допускает 12 раскрасок с 3 цветами.

Хроматический многочлен подсчитывает количество способов раскраски графа, используя не более заданного количества цветов. Например, используя цвета, график на соседнем изображении можно раскрасить 12 способами. Имея только два цвета, его вообще нельзя раскрасить. С четырьмя цветами его можно раскрасить 24 + 4⋅12 = 72 способами: используя все четыре цвета, их четыре! = 24 допустимые раскраски (присвоение четырех цветов любому четырехвершинному графу является правильной раскраской); и для каждого выбора трех из четырех цветов существует 12 допустимых трехцветных раскрасок. Итак, для графика в таблице количества допустимых раскрасок будет начинаться следующим образом:

Доступные цвета	1	2	3	4	…
Количество раскрасок	0	0	12	72	…

Хроматический полином - это функция P (G, t), которая считает количество t-раскрасок G. из названия, для данной G функция действительно является полиномом от t. Для примера графа P (G, t) = t (t - 1) (t - 2), и действительно, P (G, 4) = 72.

Хроматический полином включает в себя, по крайней мере, столько же информации о окрашиваемости G, как и о хроматическом числе. В самом деле, χ - наименьшее натуральное число, не являющееся корнем хроматического многочлена

$\chi \; (G)\; =\; min\; \{k:\; P\; (G,\; k)>0\}.\; \{\backslash \; Displaystyle\; \backslash \; чи\; (G)\; =\; \backslash \; мин\; \backslash \; \{к\; \backslash ,\; \backslash \; двоеточие\; \backslash ,\; P\; (G,\; k)>0\; \backslash \}.\}$

Цветовные многочлены для некоторых графиков 55533>Треугольник K (t - 1) (t - 2) {\ displaystyle t (t-1) (t-2)}

Полный график Kn	$t\; (t\; -\; 1)\; (t\; -\; 2)\; \cdots \; (\; t\; -\; (n\; -\; 1))\; \{\backslash \; displaystyle\; t\; (t-1)\; (t-2)\; \backslash \; cdots\; (t-\; (n-1))\}$
Дерево с n вершинами	$t\; (t\; -\; 1)\; n\; -\; 1\; \{\backslash \; displaystyle\; t\; (t-1)\; ^\; \{n-1\}\}$
Цикл Cn	$(t\; -\; 1)\; n\; +\; (-\; 1)\; n\; (t\; -\; 1)\; \{\backslash \; displaystyle\; (\; t-1)\; ^\; \{n\}\; +\; (-\; 1)\; ^\; \{n\}\; (t-1)\}$
График Петерсена	$t\; (t\; -\; 1)\; (t\; -\; 2)\; (t\; 7\; -\; 12\; t\; 6\; +\; 67\; т\; 5\; -\; 230\; т\; 4\; +\; 529\; т\; 3\; -\; 814\; т\; 2\; +\; 775\; т\; -\; 352)\; \{\backslash \; displaystyle\; t\; (t-1)\; (t-2)\; (t\; ^\; \{7\}\; -12t\; ^\; \{6\}\; +\; 67t\; ^\; \{5\}\; -\; 230t\; ^\; \{4\}\; +\; 529t\; ^\; \{3\}\; -814t\; ^\; \{2\}\; +\; 775t-352)\}$

Раскраска ребер

раскраска ребер графа - это правильная раскраска ребер, что означает присвоение цвета ребрам так, чтобы ни одна вершина не инцидентна двум ребрам такого же цвета. цветов называется k-раскраской ребер и эквивалентна задаче разбиения набора ребер на k сопоставлений. Наименьшее количество цветов, необходимое для окраски ребер графа G, - это хроматический индекс или краевое хроматическое число, χ '(G). Раскраска Тейта - это трехреберная раскраска кубического графа. Теорема о четырех цветах эквивалентна утверждению, что каждый плоский кубический граф без мостов допускает раскраску Тейта.

Тотальная раскраска

Полная раскраска - это тип раскраски на вершинах и ребрах графа. При использовании без каких-либо уточнений полной раскраска всегда считается правильным в том смысле, что никаким дополнительным вершинам, никаким смежным ребрам, никакому ребру и его конечным вершинам не назначается один и тот же цвет. Общее хроматическое число χ ″ (G) графа G - это наименьшее количество цветов, необходимое для любого общего раскраски G.

Раскраска без метки

Раскраска без метки графа Граф - это орбита раскраски под группы автоморфизмов графа. Если мы интерпретируем раскраску графа на вершинах $d\; \{\backslash \; displaystyle\; d\}$как вектор в $Z\; d\; \{\backslash \; displaystyle\; \backslash \; mathbb\; \{Z\}\; ^\; \{d\}\}$, действие автоморфизма - это перестановка коэффициентов раскраски. Существуют аналоги хроматических многочленов, которые подсчитывают количество немаркированных раскрасок графа из заданного конечного набора цветов.

Верхние границы хроматического числа

Присвоение различных цветов вершинам всегда дает правильную окраску, поэтому

$1\; \le \; \chi \; (G)\; \le \; n.\; \{\backslash \; displaystyle\; 1\; \backslash \; leq\; \backslash \; chi\; (G)\; \backslash \; leq\; n.\}$

Единственными графами, которые могут быть одноцветными, являются графами без ребер. A полный граф $K\; n\; \{\backslash \; displaystyle\; K\_\; \{n\}\}$из n вершин требует $\chi \; (K\; n)\; =\; n\; \{\backslash \; displaystyle\; \backslash \; chi\; (K\_\; \{\; n\})\; =\; n\}$цветов. В оптимальной раскраске должно быть по крайней мере одно из m ребер графа между каждой парой цветовых классов, поэтому

$\chi \; (G)\; (\chi \; (G)\; -\; 1)\; \le \; 2\; m.\; \{\backslash \; displaystyle\; \backslash \; chi\; (G)\; (\backslash \; chi\; (G)\; -1)\; \backslash \; leq\; 2m.\}$

Если G содержит клику размера k, то для раскрашивания этого требуется не менее k цветов клика; Словами, хроматическое число - это другими по крайней мере кликовое число:

$\chi \; (G)\; \ge \; \omega \; (G).\; \{\backslash \; displaystyle\; \backslash \; chi\; (G)\; \backslash \; geq\; \backslash \; omega\; (G).\}$

Для совершенных графов эта граница жесткая. Поиск клик известен как проблема клик.

Двукратные графы - это в точности двудольные графы, включая деревья и леса. По теореме о четырех цветах любой плоский граф может быть четырехцветным.

A жадная раскраска показывает, что любой граф можно раскрасить на один цвет больше, чем максимальная вершина степени,

$\chi \; (G)\; \le \; \Delta \; (G)\; +\; 1.\; \{\backslash \; displaystyle\; \backslash \; chi\; (G)\; \backslash \; leq\; \backslash \; Delta\; (G)\; +1.\}$

Полные графы имеют $\chi \; (G)\; =\; n\; \{\backslash \; displaystyle\; \backslash \; chi\; (G)\; =\; n\}$и $\Delta \; (G)\; =\; n\; -\; 1\; \{\backslash \; displaystyle\; \backslash \; Delta\; (G)\; =\; n-1\}$и нечетные циклы имеют $\chi \; (G)\; =\; 3\; \{\backslash \; displaystyle\; \backslash \; chi\; (G)\; =\; 3\}$и $\Delta \; (G)\; =\; 2\; \{\backslash \; displaystyle\; \backslash \; Delta\; (G)\; =\; 2\}$, поэтому для этих графиков эта граница является наилучшей. Во всех остальных случаях оценка может быть немного улучшена; Теорема Брукса утверждает, что

теорема Брукса : $\chi \; (G)\; \le \; \Delta \; (G)\; \{\backslash \; displaystyle\; \backslash \; chi\; (G)\; \backslash \; leq\; \backslash \; Delta\; (G)\}$для связного простого графа G, если G не является полным графом или нечетным циклом.

Нижние границы хроматического числа

За прошедшие годы было обнаружено несколько нижних границ для хроматических границ:

Граница Хоффмана: Пусть $W\; \{\backslash \; displaystyle\; W\}$будет вещественной симметричной матрицей, такой что $W\; i,\; j\; =\; 0\; \{\backslash \; displaystyle\; W\_\; \{i,\; j\}\; =\; 0\}$всякий раз, когда $(i,\; j)\; \{\backslash \; displaystyle\; (\; i,\; j)\}$не является ребром в $G\; \{\backslash \; displaystyle\; G\}$. Определите $\chi \; W\; (G)\; =\; 1\; -\; \lambda \; max\; (W)\; \lambda \; min\; (W)\; \{\backslash \; displaystyle\; \backslash \; chi\; \_\; \{W\}\; (G)\; =\; 1\; -\; \{\backslash \; tfrac\; \{\backslash \; lambda\; \_\; \{\backslash \; max\}\; (W)\}\; \{\backslash \; lambda\; \_\; \{\backslash \; min\}\; (W)\}\}\}$, где $\lambda \; max\; (W),\; \lambda \; min\; (W)\; \{\backslash \; displaystyle\; \backslash \; lambda\; \_\; \{\backslash \; max\}\; (W),\; \backslash \; lambda\; \_\; \{\backslash \; min\}\; (W)\}$- наибольшее и наименьшее собственные значения $W\; \{\backslash \; displaystyle\; W\}$. Определим $\chi \; ЧАС\; (G)\; знак\; равно\; макс.\; W\; \chi \; W\; (G)\; \{\backslash \; Displaystyle\; \backslash \; chi\; \_\; \{H\}\; (G)\; =\; \backslash \; max\; \_\; \{W\}\; \backslash \; chi\; \_\; \{W\}\; (G)\}$с $W\; \{\backslash \; displaystyle\; W\}$, как указано выше. Тогда:

$\chi \; H\; (G)\; \le \; \chi \; (G)\; \{\backslash \; displaystyle\; \backslash \; chi\; \_\; \{H\}\; (G)\; \backslash \; leq\; \backslash \; chi\; (G)\}$.

Векторное хроматическое число: Пусть $W\; \{\backslash \; displaystyle\; W\}$быть положительной полуопределенной матрицей, такой что $W\; i,\; j\; \le \; -\; 1\; k\; -\; 1\; \{\backslash \; displaystyle\; W\_\; \{i,\; j\}\; \backslash \; leq\; -\; \{\backslash \; tfrac\; \{1\}\; \{\; k-1\}\}\}$всякий раз, когда $(i,\; j)\; \{\backslash \; displaystyle\; (i,\; j)\}$является ребром в $G\; \{\backslash \; displaystyle\; G\; \}$. Определите $\chi \; V\; (G)\; \{\backslash \; displaystyle\; \backslash \; chi\; \_\; \{V\}\; (G)\}$как наименьшее k, для которого такая матрица $W\; \{\backslash \; displaystyle\; W\}$существует. Тогда

$\chi \; V\; (G)\; \le \; \chi \; (G).\; \{\backslash \; displaystyle\; \backslash \; chi\; \_\; \{V\}\; (G)\; \backslash \; leq\; \backslash \; chi\; (G).\}$

Число Ловаса : Число Ловаса дополнительного графа также является нижней границей хроматического числа:

$\vartheta \; (G\; ¯)\; \le \; \chi \; (G).\; \{\backslash \; displaystyle\; \backslash \; vartheta\; (\{\backslash \; bar\; \{G\}\})\; \backslash \; leq\; \backslash \; chi\; (G).\}$

Дробное хроматическое число : Дробное хроматическое число графа - это нижняя граница хроматического числа:

$\chi \; f\; (G)\; \le \; \chi \; (G).\; \{\backslash \; displaystyle\; \backslash \; chi\; \_\; \{f\}\; (G)\; \backslash \; leq\; \backslash \; chi\; (G).\}$

Эти границы упорядочены следующим образом:

$\chi \; H\; (G)\; \le \; \chi \; V\; (G)\; \le \; \vartheta \; (G\; ¯)\; \le \; \chi \; f\; (G)\; \le \; \chi \; (G).\; \{\backslash \; displaystyle\; \backslash \; chi\; \_\; \{H\}\; (G)\; \backslash \; leq\; \backslash \; chi\; \_\; \{V\}\; (G)\; \backslash \; leq\; \backslash \; vartheta\; (\{\backslash \; bar\; \{G\}\})\; \backslash \; leq\; \backslash \; chi\; \_\; \{f\}\; (G)\; \backslash \; leq\; \backslash \; chi\; (G).\}$

Графы с высоким хроматическим числом

Графы с большими кликами имеют высокое хроматическое число, но обратное неверно. Граф Грёча является примером 4-хроматического графа без треугольника, и этот пример можно обобщить на Mycielskians.

Теорема Mycielski (1949, Ян Мицельски 1955): Существуют графы без треугольников с произвольно высоким порядковым числом.

Согласно теореме Брукса, высшая степень. Еще одно локальное свойство, приводящее к высокому хроматическому питанию, - это наличие большого клики. Но раскрашиваемость не является полностью локальным явлением: граф с большим обхватом выглядит локально как дерево, потому что все циклы длинные, но его хроматическое число не обязательно должно быть 2:

Теорема (Эрдеш): Существуют графы произвольно большого обхвата и хроматического числа.

Границы хроматического индекса

Раскраска ребер G - это раскраска вершин его линейного графа $L\; (G)\; \{\backslash \; displaystyle\; L\; (G)\}$, и наоборот. Таким образом,

$\chi \; \prime \; (G)\; =\; \chi \; (L\; (G)).\; \{\backslash \; displaystyle\; \backslash \; chi\; \text{'}(G)\; =\; \backslash \; chi\; (L\; (G)).\}$

Существует сильная взаимосвязь между окрашиваемостью краев и максимальной степенью графа $\Delta \; (G)\; \{\backslash \; displaystyle\; \backslash \; Delta\; (G)\}$. Время всем ребрам, инцидентным одной вершине, нужен свой цвет, мы имеем

$\chi \; \prime \; (G)\; \ge \; ∆\; (G).\; \{\backslash \; displaystyle\; \backslash \; chi\; \text{'}(G)\; \backslash \; geq\; \backslash \; Delta\; (G).\}$

Кроме того,

теорема Кёнига :$\chi \; \prime \; (G)\; =\; \Delta \; (G)\; \{\backslash \; displaystyle\; \backslash \; chi\text{'}\; (G)\; =\; \backslash \; Delta\; (G)\}$, если G двудольный.

В общем, связь даже сильнее, чем то, что дает теорема Брукса для раскраски вершин:

Теорема Визинга: График максимальной степени $\Delta \; \{\backslash \; displaystyle\; \backslash \; Delta\}$имеет краевое хроматическое число $\Delta \; \{\backslash \; displaystyle\; \backslash \; Delta\}$или $\Delta \; +\; 1\; \{\backslash \; displaystyle\; \backslash \; Delta\; +1\}$.

Другие свойства

Граф имеет k-раскраску тогда и только тогда, когда он имеет ациклическую ориентацию, для которой самый длинный путь имеет длину не больше k; это теорема Галлаи - Хассе - Роя - Витавера (Nešetřil Ossona de Mendez 2012).

Для плоских графов раскраска вершин по существу двойственна потокам нигде-ноль.

О бесконечных графах известно гораздо меньше. Ниже приведены два из немногих результатов о раскраске бесконечного графа:

• Если все конечные подграфы бесконечного графа G являются k-раскрашиваемыми, то G также является раскрашиваемым в предположении аксиомы по выбору. Это теорема де Брейна – Эрдеша из de Bruijn Erds (1951).
• . Если граф допускает полную n-раскраску для любого n ≥ n 0, он допускает бесконечную полную раскраску (Фосетт 1978).

Открытые задачи

Как указано выше, $\omega \; (G)\; \le \; \chi \; (G)\; \le \; \Delta \; (G)\; +\; 1.\; \{\backslash \; displaystyle\; \backslash \; omega\; (G)\; \backslash \; leq\; \backslash \; chi\; (G)\; \backslash \; leq\; \backslash \; Delta\; (G)\; +1.\}$Гипотеза Рида 1998 года состоит в том, что значение существенно ближе к нижней границе, $\chi \; (G)\; \le \; \lceil \; \omega \; (G)\; +\; \Delta \; (G)\; +\; 1\; 2\; \rceil ,\; \{\backslash \; displaystyle\; \backslash \; chi\; (G)\; \backslash \; leq\; \backslash \; left\; \backslash \; lceil\; \{\backslash \; frac\; \{\backslash \; omega\; (G)\; +\; \backslash \; Delta\; (G)\; +\; 1\}\; \{2\}\}\; \backslash \; right\; \backslash \; rceil.\}$

Хроматическое число плоскости, где две точки являются смежными, если они имеют единичное расстояние, неизвестно, хотя это одно из 5, 6, или 7. Другие открытые проблемы, касающиеся хроматическогочисло графов, включая в себя гипотезу Хадвигера о том, что каждый граф с графическим числом имеет полный граф на k вершинах как минор, гипотеза Эрдеша - Фабера - Ловаса, ограничивающее хроматическое число о бъединений полных графов, которые имеют не более одной общей вершины для каждой пары, и гипотеза Альбертсона о том, что k-хроматических графов полные графы - это графы с наименьшим пересечения число пересечения.

Когда Биркгоф и Льюис ввели хроматический полином в атаке на теорему о четырех цветах, они предположили, что для плоских графов G полином $P\; (G,\; t)\; \{\backslash \; displaystyle\; P\; (\; G,\; t)\}$не имеет нулей в области $[4,\; \infty )\; \{\backslash \; displaystyle\; [4,\; \backslash \; infty)\}$. Хотя известно, что такой хроматический многочлен не имеет нулей в области $[5,\; \infty )\; \{\backslash \; displaystyle\; [5,\; \backslash \; infty)\}$и что $P\; (G,\; 4)\; \ne \; 0\; \{\; \backslash \; displaystyle\; P\; (G,\; 4)\; \backslash \; neq\; 0\}$, их гипотеза все еще не решена. Также остается нерешенная проблема характеризовать графы, которые имеют один и тот же хроматический многочлен, определять, какие многочлены являются хроматическими.

Раскраска графа
Решение
Имя	Раскраска графа, раскраска вершин, k-раскраска
Входные данные	График G с n вершинами. Целое число k
Выходные данные	Допускает ли G правильную раскраску вершин в k цветов?
Время выполнения	O (2n)
Сложность	NP-полная
Сокращение от	3-удовлетворяемости
Гэри - Джонсон	GT4
Оптимизация
Имя	Хроматическое число
Входные данные	График G с n вершинами.
Выходные данные	χ (G)
Сложность	NP-hard
Приближенность	O (n (log n) (log log n))
Неприближаемость	O (n), если P = NP
Проблема подсчета
Имя	Хроматический многочлен
Входные данные	График G с n вершинами. Целое число k
Выходные данные	Число P (G, k) правильных k-раскрасок G
Время выполнения	O (2n)
Сложность	# P -Полное
Аппроксимируемость	FPRAS для ограниченных случаев
Неприближаемость	Нет PTAS, если P = NP

Полиномиальное время

Определение того, можно ли раскрасить граф в 2 цвета, эквивалентно определению того, является ли граф двудольным и, следовательно, вычислимым за линейное время с использованием поиска в ширину или поиск в глубину. В более общем смысле, хроматическое число и соответствующая раскраска совершенных графов могут быть вычислены за полиномиальное время с использованием полуопределенного программирования. Замкнутые формулы для хроматического полинома известны для многих классов графов, таких как леса, хордовые графы, циклы, колеса и лестницы, поэтому их можно вычислить за полиномиальное время.

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

Точные алгоритмы

перебор для k-раскраски учитывают каждое из $kn\; \{\backslash \; displaystyle\; k\; ^\; \{n\}\}$присвоений k цветов до n вершин и проверяет каждую, допустимо ли это. Чтобы вычислить хроматическое число и хроматический многочлен, эта процедура используется для каждого $k\; =\; 1,\dots ,\; n\; -\; 1\; \{\backslash \; displaystyle\; k\; =\; 1,\; \backslash \; ldots,\; n-1\}$, непрактично для всех входных графиков, кроме самых маленьких.

Используя динамическое программирование и ограничение количества максимальных независимых множеств, k-раскрашиваемость может быть определена во времени и пространстве $O\; (2.4423\; n)\; \{\backslash \; Displaystyle\; O\; (2.4423\; ^\; \{n\})\}$. Используя принцип включения-исключения и алгоритма Йейтса для быстрого дзета-преобразования, k-окрашиваемость может быть определена за время $O\; (2\; nn)\; \{\backslash \; displaystyle\; O\; (2\; ^\; \{\; n\}\; n)\}$для любого k. Известны более быстрые алгоритмы для 3- и 4-цветовой раскраски, которая может быть определена за время $O\; (1.3289\; n)\; \{\backslash \; displaystyle\; O\; (1.3289\; ^\; \{n\})\}$и $O\; (1,7272\; n)\; \{\backslash \; displaystyle\; O\; (1,7272\; ^\; \{n\})\}$соответственно.

Сжатие

Сжатие $G\; /\; uv\; \{\backslash \; displaystyle\; G\; /\; uv\}$графа G - это граф, полученный путем идентификации вершины u и v и удалив все ребра между ними. Остальные ребра, изначально инцидентные u или v, теперь инцидентны их идентификации. Эта операция играет важную роль при анализе раскраски графов.

Хроматическое число удовлетворяет рекуррентному действию :

$\chi \; (G)\; =\; min\; \{\chi \; (G\; +\; uv),\; \chi \; (G\; /\; uv)\}\; \{\backslash \; displaystyle\; \backslash \; chi\; (G)\; =\; \{\backslash \; text\; \{min\}\}\; \backslash \; \{\backslash \; chi\; (G\; +\; uv),\; \backslash \; chi\; (G\; /\; uv)\; \backslash \}\}$

из-за Зыкова (1949), где u и v несмежны вершин, а $G\; +\; uv\; \{\backslash \; displaystyle\; G\; +\; uv\}$- граф с добавленным ребром ув. Несколько алгоритмов основаны на оценке этой повторяемости, и результирующее дерево вычислений иногда называют деревом Зыкова. Время работы основано на эвристике для выбора вершин u и v.

Хроматический многочлен удовлетворяет следующему рекуррентному использованию

$P\; (G\; -\; uv,\; k)\; =\; P\; (G\; /\; uv,\; k)\; +\; P\; (G,\; k)\; \{\backslash \; Displaystyle\; P\; (G-uv,\; k)\; =\; P\; (G\; /\; uv,\; k)\; +\; P\; (G,\; k)\}$

, где u и v - вспомогательные вершины, и $G\; -\; uv\; \{\backslash \; displaystyle\; G-uv\}$- граф с удаленным ребром ув. $P\; (G\; -\; uv,\; k)\; \{\backslash \; displaystyle\; P\; (G-uv,\; k)\}$представляет количество правильных раскрасок графа, где вершины могут иметь одинаковые или разные цвета. Тогда правильные раскраски возникают из двух разных графов. Чтобы объяснить, что имеют вершины u и v разные цвета, мы могли бы рассмотреть граф, в котором u и v смежны. Если u и v имеют одинаковые цвета, мы бы могли рассмотреть граф, в котором u и v сжаты. Тютте, любопытство по поводу того, какие другие свойства графа удовлетворяют это повторение, привело к открытию двумерного обобщения хроматического полинома, полинома Тутте.

Эти выражения приведены к рекурсивной процедуре, называемой удаленным - алгоритмом сжатия, который лежит в основе многих алгоритмов раскраски графов. Время выполнения удовлетворяет тому же результату, что и число Фибоначчи, поэтому в худшем случае алгоритм работает во времени с полиномиальным множителем $(1\; +\; 5\; 2)\; n\; +\; m\; =\; O\; (1.6180\; п\; +\; м)\; \{\backslash \; displaystyle\; \backslash \; left\; (\{\backslash \; tfrac\; \{1\; +\; \{\backslash \; sqrt\; \{5\}\}\}\; \{2\}\}\; \backslash \; right)\; ^\; \{n\; +\; m\}\; =\; O\; (1.6180\; ^\; \{n\; +\; m\})\}$для n вершин и m ребер. Анализ можно улучшить с точностью до полиномиального множителя числа $t\; (G)\; \{\backslash \; displaystyle\; t\; (G)\}$из остовных деревьев входного графа. На практике, чтобы избежать некоторых рекурсивных программ, используются стратегии ветвей и границ и отказ от изоморфизма графов. Время выполнения зависит от эвристики, используемой для выбора пары вершин.

Жадная раскраска

Две жадные раскраски одного и того же графа с использованием разных порядков вершин. Правый пример обобщается на двухцветные графы с вершинами, где жадный алгоритм расходует $n\; /\; 2\; \{\backslash \; displaystyle\; n\; /\; 2\}$цветов.

жадный алгоритм рассматривает вершины в определенном порядке $v\; 1\; \{\backslash \; displaystyle\; v\_\; \{1\}\}$,…, $vn\; \{\backslash \; displaystyle\; v\_\; \{n\}\}$и назначает в $vi\; \{\backslash \; displaystyle\; v\_\; \{i\}\}$наименьший доступный цвет, не использованный соседями $vi\; \{\backslash \; displaystyle\; v\_\; \{i\}\}$среди $v\; 1\; \{\backslash \; displaystyle\; v\_\; \{1\}\}$,…, $vi\; -\; 1\; \{\backslash \; displaystyle\; v\_\; \{i-1\}\}$, при необходимости добавляя новый цвет. Качество полученной окраски зависит от выбранной вами расцветки. Существует порядок, который приводит к жадной раскраске с оптимальным числом $\chi \; (G)\; \{\backslash \; displaystyle\; \backslash \; chi\; (G)\}$цветов. С другой стороны, жадные раскраски могут быть сколь угодно плохими; например, граф короны на вершинах может быть двухцветным, но имеет порядок, который приводит к жадной окраске с $n\; /\; 2\; \{\backslash \; displaystyle\; n\; /\; 2\}$цвета.

Для хордовых графов и для особых случаев хордовых графов, таких как интервальные графы и графы безразличия, можно использовать алгоритм жадной окраски найти оптимальные раскраски за полиномиальное время, выбрав порядок вершин, обратный порядку идеального исключения для графа. идеально упорядоченные графы содержат это свойство, но найти идеальный порядок этих графов NP-сложно.

Если вершины упорядочены в соответствии с их степенями, в результирующей жадной раскраске используется не более $max\; i\; min\; \{d\; (xi)\; +\; 1,\; i\}\; \{\backslash \; displaystyle\; \{\backslash \; text\; \{max\}\}\; \_\; \{i\}\; \{\backslash \; text\; \{min\}\}\; \backslash \; \{d\; (x\_\; \{i\})\; +\; 1,\; i\; \backslash \}\}$цветов, максимум на один больше, чем максимальная степень графика. Эту эвристику иногда называют алгоритмом Уэльса - Пауэлла. Другая эвристика, связанная с Brélaz, устанавливает порядок динамически, пока алгоритм продолжает работу, выбирая следующую вершину, соответствующую с наибольшим числом разных цветов. Многие алгоритмы альтернативного алгоритма основаны на жадной раскраске другие стратегии статической или динамической упорядочивания вершин, эти алгоритмы иногда называют алгоритмами последовательной раскраски .

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

Параллельные и распределенные алгоритмы

В области распределенных алгоритмов раскраска графов соединенных алгоритмов нарушения симметрии. Современные рандомизированные алгоритмы быстрее при достаточно большой максимальной степени Δ, чем детерминированные алгоритмы. Самые быстрые рандомизированные алгоритмы используют метод множественных испытаний Шнайдера и др.

. В симметричный графе детеррованный распределенный алгоритм не может найти правильная раскраска вершины. Некоторая вспомогательная информация необходима, чтобы нарушить симметрию. Стандартное предположение состоит в том, что изначально каждый узел имеет уникальный идентификатор, например, из набора {1, 2,..., n}. Иначе говоря, предполагаем, что нам дана n-раскраска. Задача состоит в том, чтобы уменьшить количество цветов с n, например, до Δ + 1. Чем больше цветов используется, например, O (Δ) вместо Δ + 1, требуется меньше раундов связи.

Прямая распределенная версия жадного алгоритма для (Δ + 1) -раскраски требует Θ (n) раундов связи в худшем случае - может потребоваться распространение информации с одной стороны сети на другую.

Простейший интересный случай - это n- цикл. Ричард Коул и Узи Вишкин показывают, что существует распределенный алгоритм, который уменьшает количество цветов с n до O (log n) за один синхронный шаг связи. Повторяя ту же жизнь, можно получить 3-цветную раскраску n-го цикла за цикл O (log * n) шагов связи (при условии, что у нас есть уникальные идентификаторы узлов).

Функция log *, повторный логарифм, является очень медленно растущей функцией, «почти постоянной». Следовательно, результат Коула и Вишкина поднял вопрос о том, существует ли распределенный алгоритм с постоянным временем для 3-раскраски n-цикла. Linial (1992) показал, что это невозможно: любой детерминированный распределенный алгоритм требует Ω (log * n) шагов связи для уменьшения n-раскраски до 3-раскраски в n -цикл.

Техника Коула и Вишкина также может применяться к произвольным графам ограниченной степени; время работы составляет poly (Δ) + O (log * n). Этот метод был расширен до графов единичных дисков Шнайдером и др. Самые быстрые детерминированные алгоритмы (Δ + 1) -раскрашивания для малых Δ принадлежат Леониду Баренбойму, Майклу Элькину и Фабиану Куну. Алгоритм Баренбойма и др. выполняется за время O (Δ) + log * (n) / 2, что является оптимальным с точки зрения n, поскольку постоянный множитель 1/2 не может быть улучшен из-за нижней границы Линиала. Panconesi Srinivasan (1996) использовать разложение сети для вычисления раскраски Δ + 1 во времени $2\; O\; (log\; \; n)\; \{\backslash \; displaystyle\; 2\; ^\; \{O\; \backslash \; left\; (\{\backslash \; sqrt\; \{\backslash \; log\; n\}\}\; \backslash \; right)\}\}$.

Проблема раскраски ребер также изучалась в распределенной модели. Panconesi Rizzi (2001) в этой модели достигают (2Δ - 1) -раскрашивания за O (Δ + log * n) времени. Нижняя граница для распределенной окраски вершин согласно Linial (1992) применима также к проблеме распределенной окраски ребер.

Децентрализованные алгоритмы

Децентрализованные алгоритмы - это алгоритмы, в которых передача сообщений не разрешена (в отличие от распределенных алгоритмов, в которых происходит локальная передача сообщений), и существуют эффективные децентрализованные алгоритмы, которые окрашивают график, если правильная окраска существует. Они предполагают, что вершина способна определять, использует ли какой-либо из ее соседей тот же цвет, что и вершина, то есть существует ли локальный конфликт. Это умеренное предположение во многих приложениях, например. при распределении беспроводных каналов обычно разумно предположить, что станция сможет определить, используют ли другие мешающие передатчики тот же канал (например, путем измерения SINR). Этой сенсорной информации достаточно для того, чтобы алгоритмы, основанные на обучающихся автоматах, могли найти правильную раскраску графа с вероятностью единица.

Вычислительная сложность

Раскраска графа сложна в вычислительном отношении. Это NP-полный, чтобы решить, допускает ли данный граф k-раскраску для данного k, за исключением случаев k ∈ {0,1,2}. В частности, вычислить хроматическое число NP-сложно. Проблема 3-раскраски остается NP-полной даже на 4-регулярных планарных графах. Однако для любого k>3 существует k-раскраска плоского графа по теореме о четырех цветах, и можно найти такую ​​раскраску за полиномиальное время.

Самый известный алгоритм аппроксимации вычисляет раскраску размером не более чем в пределах коэффициента O (n (log log n) (log n)) хроматического числа. Для всех ε>0 аппроксимация хроматического числа в пределах n является NP-сложной.

Также NP-сложно раскрасить трехкратный граф в 4 цвета и k-окрашиваемый граф в k цветов для достаточно больших константа k.

Вычисление коэффициентов хроматического полинома: # P-hard. Фактически, даже вычисление значения $\chi \; (G,\; k)\; \{\backslash \; displaystyle\; \backslash \; chi\; (G,\; k)\}$является # P-сложным в любой рациональной точке k за исключением k = 1 и k = 2. Не FPRAS для анализа хроматического полинома в любой рациональной точке k ≥ 1,5, за исключением k = 2, за исключением NP = RP.

для окраски краев, доказательство результата Визинга дает алгоритм, использующий не более Δ + 1 цветов. Однако выбор между двумя значениями-кандидатами для краевого хроматического числа является NP-полным. Что касается алгоритмов аппроксимации, алгоритм Визуально показывает, что хроматическое число может быть аппроксимировано с точностью до 4/3, а результат твердости показывает, что (4/3 - ε) -алгоритм не существует для любого ε>0, кроме P = NP. Это одни из самых старых результатов в литературе по аппроксимационным алгоритмам, хотя ни в одной из статей это понятие явно не используется.

Планирование

Модели раскраски вершин по числу из задач планирования. Одно из самых чистых заданий требует одного такого интервала. Задания могут быть назначены в любом порядке, но пары заданий могут быть указаны в том смысле, что они не могут быть назначены на одно и то же время, например, потому что они оба полагаются на общий ресурс. Соответствующий граф содержит вершину для каждой работы и ребро для каждой конфликтующей пары работ. Хроматическое число графа - это как раз минимальное время изготовления, оптимальное время для завершения всех работ без конфликтов.

Детали задачи определения устойчивости графа. Например, при назначении самолетов для полетов результирующий граф представляет собой интервальный граф, проблема окраски может быть решена поэтому эффективно. В распределении полосы пропускания радиостанции, результирующий графом единичного диска является графом единичного диска, поэтому проблема раскраски является 3-аппроксимируемой.

Размещение регистров

A компилятор - это компьютерная программа, которая переводит один компьютерный язык в другой. Чтобы сократить время выполнения результирующего кода одним из методов оптимизации компилятора является выделение регистров, при котором наиболее часто используемые значения скомпилированной программы хранятся в быстром регистрах процессора. В идеале значения назначаются регистры, чтобы все они могли находиться в регистрах, когда они использовались.

Хрестоматийный подход к этой проблеме в моделировании ее задачи раскраски графа. Компилятор строит интерференционный граф, в котором вершины являются переменными, а ребро соединяет две вершины, если они необходимы одновременно. Если граф можно раскрасить в k цветов, то любой набор чисел, необходимых одновременно, можно сохранить не более чем в k регистрах.

Другие приложения

Проблема раскрашивания графика во многих практических областях, таких как сопоставление с образцом, планирование занятий спортом, разработка планов рассадки, расписание экзаменов, расписание такси., а также решение судоку головоломок.

Теория Рамсея

Важный класс проблем неправильной раскраски изучается в теории Рамсея, где ребрам графа присвоены цвета, и нет ограничений на цвета инцидентных ребер. Примером является теорема о дружбе, которая утверждает, что при любом раскраске ребер $K\; 6\; \{\backslash \; displaystyle\; K\_\; \{6\}\}$полный граф из шести вершин, получится монохромный треугольник; часто изображается высказыванием, что в любой группе из шести человек есть либо три общих незнакомца, либо три общих знакомых. Теория Рамсея включает обобщение этой идеи для поиска регулярных функций беспорядка, нахождения средств существования монохроматических подграфов с заданной структурой.

Другие цвета

Общая окраска дополнительных вершин Полная окраска с дополнительным ограничением, что любые две соседние вершины имеют разные наборы цветов Ациклическая окраска Каждые 2-хроматические подграф ациклическим B-раскраска раскраска вершин, где каждый цветовой класс содержит вершину, имеющую соседа во всех других цветовых классах. Круговая раскраска На основе систем задач, в которых происходит производство циклически Совместное окрашивание Неправильная раскраска вершин, при которой каждый цветовой класс индуцирует набор или клику Полная раскраска Каждая пара цветов появляется как минимум на одном ребре Дефектная раскраска Несобственная раскраска вершин, где каждый цветовой класс индуцирует подграф ограниченной степени. Отличная раскраска Несоответствующая раскраска вершин, которая разрушает все симметрии графа Равная раскраска Размеры цветовых классов различаются не более чем на один Точная раскраска Каждая пара цвета появляется ровно на одном ребре Дробная раскраска Вершины могут иметь несколько цветов, и на каждом ребре сумма цветовых частей каждой вершины не больше одного Гамильтонова раскраска Использует самый длинный путь между двумя вершинами, также как обходное расстояние Гармоничная раскраска Каждая пара цветов проявляется не более чем на одном ребре Раскраска инцидентности каждая смежная встреча вершины и ребра окрашена в разные цвета. цвета Интервальная раскраска ребер Цвет ребер, пересекающихся в общей вершине, должен быть смежным Раскраска списка Каждая вершина выбирает из списка цветов Раскраска ребер списка Каждое ребро выбирает из списка цветов L (h, k) -раскрашивание Разница цветов в соседних вершинах не менее h, а разница цветов вершин на расстоянии два не менее k. Частным случаем является L (2,1) -раскраска.

Ориентированная раскраска Учитывает ориентацию ребер графа Раскраска пути Моделирует задачу маршрутизации в графах Радио-раскраска Сумма расстояния между вершинами и разницы их цветов больше k + 1, где k - положительное целое число. Раскраска ранга Если две вершины имеют одинаковый цвет i, все пути между ними содержат вершину с цветом больше, чем i Подкраска Неправильная раскраска вершин, где каждый цветовой класс индуцирует объединение клик Суммарная окраска Критерием минимизации является сумма цветов Раскраска звездой Каждый 2-хроматический подграф представляет собой непересекающийся набор звезд Сильная окраска Каждый цвет появляется в каждом разделе равного размера ровно один раз Края окрашены так, что каждый цветовой класс создает сопоставление (эквивалент раскрашивания квадрата линейного графика) T-раскраска Абсолютное значение разницы между двумя цветами соседних вершин не должно принадлежать фиксированному набору T Общая окраска Вершины и ребра окрашены Центрированная окраска Каждый связанный индуцированный подграф имеет цвет, который используется ровно один раз Раскраска ребер без треугольнико в Ребра раскрашены так, что каждый цветовой класс образует без треугольников подграф Слабая раскраска Неправильная раскраска вершин, где каждый неизолированный узел хотя бы одного соседа с цветом

. Цвета также могут быть рассмотрены для графиков со знаком и графиков усиления.

На Викискладе есть медиафайлы, связанные с Раскраска графа.

• Раскраска краев
• Круговая раскраска
• Критический граф
• Гомоморфизм графа
• Конструкция Хаджоса
• Математика судоку
• Многодольный граф
• Граф с уникальной раскраской
• Граф игра-раскраска
• Интервальная окраска краев

• Высокопроизводительные алгоритмы раскраски графиков Набор из 8 различных алгоритмов (реализованные на C ++), использованный в книге Руководство по раскраске графиков: алгоритмы и приложения (Springer International Publishers, 2015).
• Страница раскраски графика Джозефа Калберсона (программы раскраски графов)
• CoLoRaTiOn Джима Эндрюса и Майка Феллоуз - головоломка с раскраской графа
• Ссылки на исходные коды Раскраска графика
• Код для эффективного вычисления Тутте, Хроматических полиномов и Полиномов потока Гэри Хаггарда, Дэвида Дж. Пирс и Гордон Ройл
• Граф, раскрашивающий веб-приложение, Хосе Антонио Мартин Х.

=== !!! == Знак равно <2>{\ Displaystyle \ чи _ {е} (G) \ Leq \ чи (G).} <2><3>{\ Displaystyle \ омега (G) \ Leq \ чи (G) \ Leq \ Delta (G) +1.} <3><4>\ Delta (G) = 2 <4><5>P (G, 4) \ neq 0 <5><6>\ chi <6><7>[5, \ infty) <7><8>{\ displaystyle 1 \ leq \ chi (G) \ leq n.} <8><9>\ chi (G) = n <9><10>t (t- 1) (t-2) <10><11>{\ text {max}} _ {i} {\ text {min}} \ {d (x_ {i}) + 1, i \} <11><12>G-uv <12><13>O (1,7272 ^ {n}) <13><14>\ chi _ {H} (G) = \ max _ {W} \ chi _ { W} (G) <14><15>{\ displaystyle \ left ({\ tfrac {1 + {\ sq rt {5}}} {2}} \ right) ^ {n + m} = O (1.6180 ^ {n + m})} <15><16>k = 1, \ ldots, n-1 <16><17>(i,j)<17><18>L(G)<18><19>G <19><20>G + uv <20><21>n / 2 <21><22>\ ци (G) \ Leq \ Delta (G) <22><23>\ chi (G, k) <23><24>{\ displaystyle O (2.4423 ^ {n})} <24><25>\ chi (G) = {\ text {min}} \ {\ chi (G + uv), \ chi ( G / uv) \} <25><26>\ Delta <26><27>{\ displaystyle \ chi _ {W} (G) = 1 - {\ tfrac {\ lambda _ {\ max} (W)} {\ лямбда _ {\ мин} (W)}}} <27><28>{\ displaystyle \ chi (G) (\ chi (G) -1) \ leq 2m.} <28><29>O (1.3289 ^ {n}) <29><30>\ Delta +1 <30><31>\ chi (G) = \ min \ {k \, \ двоеточие \, P (G, k)>0 \}. <31><32>\ chi (K_ {n}) = n <32><33>\ chi (G) = 3 <33><34>{\ displaystyle W_ {i, j} \ leq - {\ tfrac {1} {k-1}}} <34><35>v_ {n} <35><36>G / uv <36><37>\ chi _ {H} (G) \ leq \ chi (G) <37><38>{\ displaystyle \ chi <38><39>d<39><40>v_ {я-1} <40><41>к ^ {n} <41><42>O ( 2 ^ {n} n) <42><43>{\ displaystyle \ chi _ {H} (G) \ leq \ chi _ {V} (G) \ leq \ vartheta ({\ bar {G}}) \ leq \ chi _ {f} (G) \ leq \ chi (G).} <43><44>v_ {1} <44><45>\ Delta (G) = n-1 <45><46>t (t-1) (t-2) (t ^ {7} -12t ^ {6} + 67t ^ {5} -230t ^ {4} + 529t ^ {3} -814t ^ {2} + 775t- 352) <46><47>{\ displaystyle \ vartheta ({\ b ar {G}}) \ leq \ chi (G).} <47><48>\ chi (G) <48><49>P (G-uv, k) = P (G / uv, k) + P (G, k) <49><50>\ chi _ {V} (G) <50><51>K_ {6} <51><52>t (G) <52><53>t (t -1) ^ {n-1} <53><54>(t-1) ^ {n} + (- 1) ^ {n} (t-1) <54><55>[4, \ infty) <55><56>{\ displaystyle \ chi (G) \ leq \ left \ lceil {\ frac {\ omega (G) + \ Delta ( G) +1} {2}} \ right \ rceil.} <56><57>п (G, t) <57><58>{\ displaystyle \ chi _ {V} (G) \ leq \ чи (G).} <58><59>{\ displaystyle \ chi (G) \ leq \ Delta (G) +1.} <59><60>2 ^ {O \ left ({\ sqrt {\ log n}} \ right)} <60><61>K_ {n} <61><62>W_ {i, j} = 0 <62><63>v_ {i} <63><64>3-раскраскаEx.svg <64><65>{\ displaystyle \ lambda _ {\ max} (W), \ lambda _ {\ min} (W)} <65><66>\ mathbb {Z} ^ {d } <66><67>t (t-1) (t-2) \ cdots (t - (п-1)) <67><68>{\ displaystyle \ chi (G) \ geq \ omega (G).} <68><69>\ Delta (G) <69><70>W <70><71>P (G-uv, k) <71>html