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

Все неизоморфные графы с 3 вершинами и их хроматические многочлены, по часовой стрелке сверху. Независимый 3-набор: $k\; 3\; \{\backslash \; displaystyle\; k\; ^\; \{3\}\}$. Ребро и одна вершина: $k\; 2\; (k\; -\; 1)\; \{\backslash \; displaystyle\; k\; ^\; \{2\}\; (k-1)\}$. 3-путь: $k\; (k\; -\; 1)\; 2\; \{\backslash \; displaystyle\; k\; (k-1)\; ^\; \{2\}\}$. 3-клика: $k\; (k\; -\; 1)\; (k\; -\; 2)\; \{\backslash \; displaystyle\; k\; (k-1)\; (k-2)\}$.

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

• 1 История
• 2 Определение
  • 2.1 Удаление – сокращение
• 3 Примеры
• 4 Свойства
  • 4.1 Хроматическая эквивалентность
  • 4.2 Хроматические корни
  • 4.3 Раскраска с использованием всех цветов
  • 4.4 Категоризация
• 5 Алгоритмы
  • 5.1 Эффективные алгоритмы
  • 5.2 Удаление – сжатие
  • 5.3 Метод куба
  • 5.4 Вычислительная сложность
• 6 Примечания
• 7 Ссылки
• 8 Внешние ссылки

Джордж Дэвид Биркгоф представил хроматический полином в 1912 году, определив его только для плоских графов, в попытке доказать теорему о четырех цветах. Если $P\; (G,\; k)\; \{\backslash \; displaystyle\; P\; (G,\; k)\}$обозначает количество правильных раскрасок G с помощью k цветов, то можно установить теорему о четырех цветах, показав $P\; (G,\; 4)>0\; \{\backslash \; displaystyle\; P\; (G,\; 4)>0\}$для всех плоских графов G. Таким образом он надеялся применить мощные инструменты анализа и алгебры для изучения корней многочленов в проблеме комбинаторной раскраски.

Хасслер Уитни обобщил полином Биркгофа с плоского случая на общие графы в 1932 году. В 1968 году Рид спросил, какие многочлены являются хроматическими многочленами некоторого графа, вопрос, который остается открытым, и ввел концепция хроматически эквивалентных графов. Сегодня хроматические многочлены являются одним из центральных объектов теории алгебраических графов.

Все правильные раскраски вершин вершинных графов с 3 вершины с использованием k цветов для $k\; =\; 0,\; 1,\; 2,\; 3\; \{\backslash \; displaystyle\; k\; =\; 0,1,2,3\}$. Хроматический многочлен каждого графа интерполируется по количеству правильных раскрасок.

Для графа G $P\; (G,\; k)\; \{\backslash \; displaystyle\; P\; (G,\; k)\}$подсчитывает число его (собственных) вершинных k-раскрасок. Другие часто используемые обозначения включают $PG\; (k)\; \{\backslash \; displaystyle\; P\_\; \{G\}\; (k)\}$, $\chi \; G\; (k)\; \{\backslash \; displaystyle\; \backslash \; chi\; \_\; \{G\}\; (k)\}$, или $\pi \; G\; (k)\; \{\backslash \; displaystyle\; \backslash \; pi\; \_\; \{G\}\; (k)\}$. Существует уникальный полином $P\; (G,\; x)\; \{\backslash \; displaystyle\; P\; (G,\; x)\}$, который вычисляется для любого целого числа k ≥ 0 и совпадает с $P\; (Г,\; к)\; \{\backslash \; Displaystyle\; P\; (G,\; k)\}$; он называется хроматическим многочленом от G.

Например, чтобы раскрасить граф путей $P\; 3\; \{\backslash \; displaystyle\; P\_\; \{3\}\}$на 3 вершинах с k цветов, можно выбрать любой из k цветов для первой вершины, любой из $k\; -\; 1\; \{\backslash \; displaystyle\; k-1\}$оставшихся цветов для вторая вершина и, наконец, для третьей вершины любой из цветов $k\; -\; 1\; \{\backslash \; displaystyle\; k-1\}$, которые отличаются от цветов, выбранных второй вершиной. Следовательно, $P\; (P\; 3,\; k)\; =\; k\; \cdot \; (k\; -\; 1)\; \cdot \; (k\; -\; 1)\; \{\backslash \; displaystyle\; P\; (P\_\; \{3\},\; k)\; =\; k\; \backslash \; cdot\; (k-1)\; \backslash \; cdot\; (\; k-1)\}$- количество k-раскрасок $P\; 3\; \{\backslash \; displaystyle\; P\_\; \{3\}\}$. Для переменной x (не обязательно целого числа), таким образом, $P\; (P\; 3,\; x)\; =\; x\; (x\; -\; 1)\; 2\; =\; x\; 3\; -\; 2\; x\; 2\; +\; x\; \{\backslash \; displaystyle\; P\; (P\_\; \{3\},\; x)\; =\; x\; (x-1)\; ^\; \{2\}\; =\; x\; ^\; \{3\}\; -2x\; ^\; \{2\}\; +\; x\}$. (Раскраски, которые различаются только перестановкой цветов или автоморфизмами группы G, по-прежнему считаются разными.)

Удаление – сжатие

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

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

Эквивалентно, если $u\; \{\backslash \; displaystyle\; u\}$и $v\; \{\backslash \; displaystyle\; v\}$не являются смежными в G и $G\; +\; uv\; \{\backslash \; displaystyle\; G\; +\; uv\}$- это граф с ребром $uv\; \{\backslash \; displaystyle\; uv\}$добавлено, тогда

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

Это следует из наблюдения, что каждая k-раскраска G дает разные цвета для $u\; \{\backslash \; displaystyle\; u\}$и $v\; \{\backslash \; displaystyle\; v\}$или тех же цветов. В первом случае это дает (правильную) k-раскраску $G\; +\; uv\; \{\backslash \; displaystyle\; G\; +\; uv\}$, а во втором случае - раскраску $G\; /\; uv.\; \{\backslash \; Displaystyle\; G\; /\; uv\}$. И наоборот, каждую k-раскраску G можно однозначно получить из k-раскраски $G\; +\; uv\; \{\backslash \; displaystyle\; G\; +\; uv\}$или $G\; /\; uv\; \{\backslash \; displaystyle\; G\; /\; uv\; \}$(если $u\; \{\backslash \; displaystyle\; u\}$и $v\; \{\backslash \; displaystyle\; v\}$не являются смежными в G).

Следовательно, хроматический полином может быть рекурсивно определен как

$P\; (G,\; x)\; =\; xn\; \{\backslash \; displaystyle\; P\; (G,\; x)\; =\; x\; ^\; \{n\}\}$для граф без ребер на n вершинах и

$P\; (G,\; x)\; =\; P\; (G\; -\; uv,\; x)\; -\; P\; (G\; /\; uv,\; x)\; \{\backslash \; displaystyle\; P\; (G,\; x)\; =\; P\; (G-uv,\; x)\; -P\; (G\; /\; uv,\; x)\}$для графа G с ребром $uv\; \{\backslash \; displaystyle\; uv\}$(произвольно выбранный).

Поскольку количество k-раскрасок графа без ребер действительно равно $kn\; \{\backslash \; displaystyle\; k\; ^\; \{n\}\}$, по индукции по количеству ребер следует, что для всех G многочлен $P\; (G,\; x)\; \{\backslash \; displaystyle\; P\; (G,\; x)\}$совпадает с количеством k-раскрасок в каждой целой точке x = k. В частности, хроматический многочлен - это единственный интерполирующий многочлен степени не выше n через точки

$\{(0,\; P\; (G,\; 0)),\; (1,\; P\; (G,\; 1)),\; \cdots ,\; (n,\; P\; (G,\; n))\}.\; \{\backslash \; Displaystyle\; \backslash \; left\; \backslash \; \{(0,\; P\; (G,\; 0)),\; (1,\; P\; (G,\; 1)),\; \backslash \; cdots,\; (n,\; P\; (G,\; n))\; \backslash \; right\; \backslash \}.\}$

Любопытство Тютта о том, какие другие графовые инварианты удовлетворяют таким повторениям, привело его к открытию двумерного обобщения хроматического полинома, полинома Тутте $TG\; (x,\; y)\; \{\backslash \; displaystyle\; T\_\; \{G\}\; (x,\; y)\}$.

Хроматические многочлены для некоторых графов

Треугольник $K\; 3\; \{\backslash \; displaystyle\; K\_\; \{3\}\}$	$x\; (x\; -\; 1)\; (x\; -\; 2)\; \{\backslash \; displaystyle\; x\; (x-1)\; (x-2)\}$
Полный график $K\; n\; \{\backslash \; displaystyle\; K\_\; \{n\}\}$	$x\; (x\; -\; 1)\; (x\; -\; 2)\; \cdots \; (x\; -\; (n\; -\; 1))\; \{\backslash \; displaystyle\; x\; (x-1)\; (x-2)\; \backslash \; cdots\; (x-\; (n-1))\}$
граф без ребер $K\; ¯\; n\; \{\backslash \; displaystyle\; \{\backslash \; overline\; \{K\}\}\; \_\; \{n\}\}$	$xn\; \{\backslash \; displaystyle\; x\; ^\; \{n\}\}$
График пути $P\; n\; \{\; \backslash \; displaystyle\; P\_\; \{n\}\}$	$x\; (x\; -\; 1)\; n\; -\; 1\; \{\backslash \; displaystyle\; x\; (x-1)\; ^\; \{n-1\}\}$
Любое дерево на n вершинах	$Икс\; (Икс\; -\; 1)\; n\; -\; 1\; \{\backslash \; displaystyle\; x\; (x-1)\; ^\; \{n-1\}\}$
Цикл $C\; n\; \{\backslash \; displaystyle\; C\_\; \{n\}\}$	$(х\; -\; 1)\; п\; +\; (-\; 1)\; п\; (\; x\; -\; 1)\; \{\backslash \; displaystyle\; (x-1)\; ^\; \{n\}\; +\; (-\; 1)\; ^\; \{n\}\; (x-1)\}$
график Петерсена	$x\; (x\; -\; 1)\; (x\; -\; 2)\; (x\; 7\; -\; 12\; x\; 6\; +\; 67\; x\; 5\; -\; 230\; x\; 4\; +\; 529\; x\; 3\; -\; 814\; x\; 2\; +\; 775\; x\; -\; 352)\; \{\backslash \; displaystyle\; x\; (x-1)\; (x-2)\; \backslash \; left\; (x\; ^\; \{7\; \}\; -12x\; ^\; \{6\}\; +\; 67x\; ^\; \{5\}\; -230x\; ^\; \{4\}\; +\; 529x\; ^\; \{3\}\; -814x\; ^\; \{2\}\; +\; 775x-352\; \backslash \; right)\}$

Для фиксированный G на n вершинах, хроматический многочлен $P\; (G,\; x)\; \{\backslash \; displaystyle\; P\; (G,\; x)\}$является monic многочленом степени ровно n, с целочисленные коэффициенты.

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

$\chi \; (G)\; =\; min\; \{k\; \in \; N:\; P\; (G,\; k)>0\}.\; \{\backslash \; displaystyle\; \backslash \; chi\; (G)\; =\; \backslash \; min\; \backslash \; \{k\; \backslash \; in\; \backslash \; mathbb\; \{N\}:\; P\; (G,\; k)>0\; \backslash \}.\}$

Полином оценен как <\235>- 1 displaystyle -1}, то есть $P\; (G,\; -\; 1)\; \{\backslash \; displaystyle\; P\; (G,\; -1)\}$, дает $(-\; 1)\; |\; V\; (G)\; |\; \{\backslash \; displaystyle\; (-1)\; ^\; \{|\; V\; (G)\; |\}\}$, умноженное на количество ациклических ориентаций G.

производная, вычисленная как 1, $P\; \text{'}(G,\; 1)\; \{\backslash \; displaystyle\; P\text{'}\; (G,\; 1)\}$равняется $\theta \; (G)\; \{\backslash \; displaystyle\; \backslash \; theta\; (G)\}$до знака.

Если G имеет n вершин и c компонентов $G\; 1,\; \cdots ,\; G\; c\; \{\backslash \; displaystyle\; G\_\; \{1\},\; \backslash \; cdots,\; G\_\; \{c\}\}$, затем

• Коэффициенты $x\; 0,\; \cdots ,\; xc\; -\; 1\; \{\backslash \; displaystyle\; x\; ^\; \{0\},\; \backslash \; cdots,\; x\; ^\; \{c-1\}\; \}$- нули.
• Коэффициенты $xc,\; \cdots ,\; xn\; \{\backslash \; displaystyle\; x\; ^\; \{c\},\; \backslash \; cdots,\; x\; ^\; \{n\}\}$все ненулевые и чередуются в знаках.
• Коэффициент $xn\; \{\backslash \; displaystyle\; x\; ^\; \{n\}\}$равен 1 (многочлен monic ).
• Коэффициент $xn\; -\; 1\; \{\backslash \; displaystyle\; x\; ^\; \{n-1\}\}$равно $-\; |\; E\; (G)\; |\; \{\backslash \; displaystyle\; -\; |\; E\; (G)\; |\}$.

Доказательство- Просмотр, щелкнув [показать] - Мы докажем это индукцией по количеству ребер на простом графе G с $n\; \{\backslash \; displaystyle\; n\}$вершин и $k\; \{\backslash \; displaystyle\; k\}$ребер. Когда $k\; =\; 0\; \{\backslash \; displaystyle\; k\; =\; 0\}$, G - пустой график. Следовательно, согласно определению $P\; (G,\; x)\; =\; x\; n\; \{\backslash \; displaystyle\; P\; (G,\; x)\; =\; x\; ^\; \{n\}\}$. Таким образом, коэффициент при $xn\; -\; 1\; \{\backslash \; displaystyle\; x\; ^\; \{n-1\}\}$равен $0\; \{\backslash \; displaystyle\; 0\}$, что означает, что утверждение верно для пустого графа. Когда $k\; =\; 1\; \{\backslash \; displaystyle\; k\; =\; 1\}$, как в G имеет только одно ребро, $P\; (G,\; x)\; =\; xn\; -\; xn\; -\; 1\; \{\backslash \; displaystyle\; P\; (\; G,\; x)\; =\; x\; ^\; \{n\}\; -x\; ^\; \{n-1\}\}$. Таким образом, коэффициент $x\; n\; -\; 1\; \{\backslash \; displaystyle\; x\; ^\; \{n-1\}\}$равен $-\; 1\; =\; -\; |\; E\; (G)\; |\; \{\backslash \; displaystyle\; -1\; =\; -\; |\; E\; (G)\; |\}$. Таким образом, утверждение верно для k = 1. Используя сильную индукцию, предположим, что утверждение верно для $k\; =\; 0,\; 1,\; 2,...\; (к\; -\; 1)\; \{\backslash \; Displaystyle\; к\; =\; 0,1,2,...\; (к-1)\}$. Пусть G имеет $k\; \{\backslash \; displaystyle\; k\}$ребер. По принципу сокращения-удаления,

$P\; (G,\; x)\; =\; P\; (G\; -\; e,\; x)\; -\; P\; (G\; /\; e,\; x)\; \{\backslash \; displaystyle\; P\; (G,\; x)\; =\; P\; (Ge,\; x)\; -P\; (G\; /\; e,\; x)\}$,

Пусть $P\; (G\; -\; e,\; x)\; =\; xn\; -\; an\; -\; 1\; xn\; -\; 1\; +\; an\; -\; 2\; xn\; -\; 2\; -...\; \{\backslash \; Displaystyle\; P\; (Ge,\; x)\; =\; x\; ^\; \{n\}\; -a\_\; \{n-1\}\; x\; ^\; \{n-1\}\; +\; a\_\; \{n-2\}\; x\; ^\; \{n-2\}\; -...\}$и $P\; (G.\; E,\; x)\; =\; xn\; -\; 1\; -\; bn\; -\; 2\; xn\; -\; 2\; +\; bn\; -\; 3\; xn\; -\; 3\; -...\; \{\backslash \; Displaystyle\; P\; (Ge,\; x)\; =\; x\; ^\; \{n-1\}\; -b\_\; \{n-2\}\; x\; ^\; \{n-2\}\; +\; b\_\; \{n-3\}\; x\; ^\; \{n-3\}\; -...\}$.. Следовательно, $P\; (G,\; x)\; =\; xn\; -\; (an\; -\; 1\; +\; 1)\; xn\; -\; 1\; +...\; \{\backslash \; displaystyle\; P\; (G,\; x)\; =\; x\; ^\; \{n\}\; -\; (a\_\; \{n-1\}\; +1)\; x\; ^\; \{n-1\}\; +...\}$.. Поскольку $G\; -\; e\; \{\backslash \; displaystyle\; Ge\}$получается из G удалением только одного ребра e, $an\; -\; 1\; =\; k\; -\; 1\; \{\backslash \; displaystyle\; a\_\; \{n-1\}\; =\; k-1\}$, поэтому $an\; -\; 1\; +\; 1\; =\; k\; \{\backslash \; displaystyle\; a\_\; \{n-1\}\; +\; 1\; =\; k\}$и, таким образом, утверждение верно для k.

• Коэффициент при $x\; 1\; \{\backslash \; displaystyle\; x\; ^\; \{1\}\}$равен $(-\; 1)\; n\; -\; 1\; \{\backslash \; displaystyle\; (-1)\; ^\; \{n-1\}\; \}$, умноженное на количество ациклических ориентаций, которые имеют уникальный сток, в указанной произвольно выбранной вершине.
• Абсолютные значения коэффициентов каждого хроматического полинома образуют логарифмически вогнутую форму. последовательность.
• $P\; (G,\; x)\; знак\; равно\; P\; (G\; 1,\; x)\; P\; (G\; 2,\; x)\; \cdots \; P\; (G\; c,\; x)\; \{\backslash \; displaystyle\; \backslash \; scriptstyle\; P\; (G,\; x)\; =\; P\; (G\_\; \{1\; \},\; x)\; P\; (G\_\; \{2\},\; x)\; \backslash \; cdots\; P\; (G\_\; \{c\},\; x)\}$

Последнее свойство обобщается тем, что если G является k-кликовой суммой из $G\; 1\; \{\backslash \; displaystyle\; G\_\; \{1\}\}$и $G\; 2\; \{\backslash \; displaystyle\; G\_\; \{2\}\}$(т. Е. График, полученный склейкой два в клике на k вершинах), то

$P\; (G,\; x)\; =\; P\; (G\; 1,\; x)\; P\; (G\; 2,\; x)\; x\; (x\; -\; 1)\; \cdots \; (x\; -\; k\; +\; 1).\; \{\backslash \; Displaystyle\; P\; (G,\; x)\; =\; \{\backslash \; гидроразрыва\; \{P\; (G\_\; \{1\},\; x)\; P\; (G\_\; \{2\},\; x)\}\; \{x\; (x-1)\; \backslash \; cdots\; (x-k\; +\; 1)\}\; \}.\}$

Граф G с n вершинами является деревом тогда и только тогда, когда

$P\; (G,\; x)\; =\; x\; (x\; -\; 1)\; n\; -\; 1.\; \{\backslash \; displaystyle\; P\; (G,\; x)\; =\; x\; (x-1)\; ^\; \{n-1\}.\}$

Хроматическая эквивалентность

Три графика с хроматическим полиномом, равным $(x\; -\; 2)\; (\; x\; -\; 1)\; 3\; x\; \{\backslash \; displaystyle\; (x-2)\; (x-1)\; ^\; \{3\}\; x\}$.

Два графа называются хроматически эквивалентными, если они имеют один и тот же хроматический многочлен. Изоморфные графы имеют один и тот же хроматический полином, но неизоморфные графы могут быть хроматически эквивалентными. Например, все деревья на n вершинах имеют один и тот же хроматический полином. В частности, $(x\; -\; 1)\; 3\; x\; \{\backslash \; displaystyle\; (x-1)\; ^\; \{3\}\; x\}$является хроматическим многочленом как для графа когтей, так и для граф путей на 4 вершинах.

Граф хроматически уникален, если он определяется своим хроматическим полиномом с точностью до изоморфизма. Другими словами, G хроматически уникален, тогда $P\; (G,\; x)\; =\; P\; (H,\; x)\; \{\backslash \; displaystyle\; P\; (G,\; x)\; =\; P\; (H,\; x)\}$будет следует, что G и H изоморфны. Все графы цикла хроматически уникальны.

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

A корень (или ноль) хроматического многочлена, называемого «хроматическим корнем», - это значение x, где $P\; (G,\; x)\; =\; 0\; \{\backslash \; displaystyle\; P\; (G,\; x)\; =\; 0\}$. Хроматические корни были очень хорошо изучены. Фактически, первоначальная мотивация Биркгофа для определения хроматического полинома заключалась в том, чтобы показать, что для плоских графов $P\; (G,\; x)>0\; \{\backslash \; displaystyle\; P\; (G,\; x)>0\}$для x ≥ 4. Это установило бы теорему о четырех цветах.

Ни один граф не может быть 0-цветным, поэтому 0 всегда является хроматическим корнем. граф с хотя бы одним ребром. С другой стороны, за исключением этих двух точек, ни один граф не может иметь хроматический корень с действительным числом, меньшим или равным 32/27. Результат Тутте соединяет золотое сечение $\varphi \; \{\backslash \; displaystyle\; \backslash \; phi\}$с изучением хроматических корней, показывающим, что хроматические корни существуют очень близко к $\varphi \; 2\; \{\backslash \; displaystyle\; \backslash \; phi\; ^\; \{2\}\}$: если $G\; n\; \{\backslash \; displaystyle\; G\_\; \{n\}\}$является pl при арной триангуляции сферы

$P\; (G\; n,\; \varphi \; 2)\; \le \; \varphi \; 5\; -\; n.\; \{\backslash \; displaystyle\; P\; (G\_\; \{n\},\; \backslash \; phi\; ^\; \{2\})\; \backslash \; leq\; \backslash \; phi\; ^\; \{5-n\}.\}$

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

Раскраски с использованием всех цветов

Для графа G на n вершинах, пусть $ek\; \{\backslash \; displaystyle\; e\_\; \{k\}\}$обозначает количество раскрасок с использованием ровно k цветов с точностью до переименования цветов (чтобы цвета, которые могли быть полученными друг от друга перестановкой цветов, считаются как один; раскраски, полученные с помощью автоморфизмов группы G, по-прежнему считаются отдельно). Другими словами, $ek\; \{\backslash \; displaystyle\; e\_\; \{k\}\}$подсчитывает количество разделов набора вершин на k (непустых) независимых наборов. Тогда $к!\; \cdot \; e\; k\; \{\backslash \; displaystyle\; k!\; \backslash \; Cdot\; e\_\; \{k\}\}$подсчитывает количество раскрасок, используя ровно k цветов (с различимыми цветами). Для целого числа x все x-раскраски G могут быть однозначно получены путем выбора целого числа k ≤ x, выбора k цветов из имеющихся x и раскраски с использованием именно этих k (различимых) цветов. Следовательно:

$P\; (G,\; x)\; =\; \sum \; k\; =\; 0\; x\; (x\; k)\; k!\; \cdot \; ЭК\; знак\; равно\; \sum \; К\; знак\; равно\; 0\; Икс\; (Икс)\; К\; \cdot \; ЭК\; \{\backslash \; Displaystyle\; P\; (G,\; x)\; =\; \backslash \; sum\; \_\; \{k\; =\; 0\}\; ^\; \{x\}\; \{\backslash \; binom\; \{x\}\; \{k\}\}\; к!\; \backslash \; Cdot\; e\_\; \{k\}\; =\; \backslash \; sum\; \_\; \{k\; =\; 0\}\; ^\; \{x\}\; (x)\; \_\; \{k\}\; \backslash \; cdot\; e\_\; \{k\}\}$,

где $(x)\; k\; =\; x\; (x\; -\; 1)\; (\; Икс\; -\; 2)\; \cdots \; (Икс\; -\; К\; +\; 1)\; \{\backslash \; Displaystyle\; (х)\; \_\; \{к\}\; =\; х\; (х-1)\; (х-2)\; \backslash \; cdots\; (х-к\; +\; 1)\}$обозначает факториал падения. Таким образом, числа $ek\; \{\backslash \; displaystyle\; e\_\; \{k\}\}$являются коэффициентами многочлена $P\; (G,\; x)\; \{\backslash \; displaystyle\; P\; (G,\; x)\}$в основании $1,\; (x)\; 1,\; (x)\; 2,\; (x)\; 3,\dots \; \{\backslash \; displaystyle\; 1,\; (x)\; \_\; \{1\},\; (x)\; \_\; \{2\},\; (x)\; \_\; \{3\},\; \backslash \; dots\}$падающих факториалов.

Пусть $ak\; \{\backslash \; displaystyle\; a\_\; \{k\}\}$будет k-м коэффициентом $P\; (G,\; x)\; \{\backslash \; displaystyle\; P\; (G,\; x)\; \}$в стандартном базисе $1,\; x,\; x\; 2,\; x\; 3,\dots \; \{\backslash \; displaystyle\; 1,\; x,\; x\; ^\; \{2\},\; x\; ^\; \{3\},\; \backslash \; dots\}$, то есть:

$P\; (G,\; x)\; =\; \sum \; k\; =\; 0\; nakxk\; \{\backslash \; displaystyle\; P\; (G,\; x)\; =\; \backslash \; sum\; \_\; \{k\; =\; 0\}\; ^\; \{n\}\; a\_\; \{k\}\; x\; ^\; \{k\}\}$

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

$ak\; =\; \sum \; j\; =\; 0\; n\; (-\; 1)\; j\; -\; k\; [jk]\; ej\; \{\backslash \; displaystyle\; a\_\; \{k\}\; =\; \backslash \; sum\; \_\; \{j\; =\; 0\}\; ^\; \{n\}\; (-\; 1)\; ^\; \{\; jk\}\; \{\backslash \; begin\; \{bmatrix\}\; j\; \backslash \backslash \; k\; \backslash \; end\; \{bmatrix\}\}\; e\_\; \{j\}\}$и $ek\; =\; \sum \; j\; =\; 0\; n\; \{jk\}\; aj\; \{\backslash \; displaystyle\; e\_\; \{k\; \}\; =\; \backslash \; sum\; \_\; \{j\; =\; 0\}\; ^\; \{n\}\; \{\backslash \; begin\; \{Bmatrix\}\; j\; \backslash \backslash \; k\; \backslash \; end\; \{Bmatrix\}\}\; a\_\; \{j\}\}$.

Категоризация

Хроматический полином категоризован теорией гомологии, тесно связанной с гомологией Хованова.

Хроматический многочлен
Входные данные	График G с n вершинами.
Выходные данные	Коэффициенты $P\; (G,\; x)\; \{\backslash \; displaystyle\; P\; (G,\; x)\}$
Время выполнения	$O\; (2\; nnr)\; \{\backslash \; displaystyle\; O\; (2\; ^\; \{n\}\; n\; ^\; \{\; r\})\}$для некоторой константы $r\; \{\backslash \; displaystyle\; r\}$
Сложность	#P -hard
Уменьшение с	# 3SAT

# k- раскраски
Входные	График G с n вершинами.
Выходные	$P\; (G,\; k)\; \{\backslash \; displaystyle\; P\; (G,\; k)\}$
Время работы	В P для $k\; =\; 0,\; 1,\; 2\; \{\backslash \; displaystyle\; k\; =\; 0,1,2\}$. $O\; (1.6262\; n)\; \{\backslash \; displaystyle\; O\; (1.6262\; ^\; \{n\})\}$для $k\; =\; 3\; \{\backslash \; displaystyle\; k\; =\; 3\}$. В противном случае $O\; (2\; nnr)\; \{\backslash \; displaystyle\; O\; (2\; ^\; \{n\}\; n\; ^\; \{r\})\}$для некоторой константы $r\; \{\backslash \; displaystyle\; r\}$
Сложность	#P -hard, если $k\; =\; 0,\; 1,\; 2\; \{\backslash \; displaystyle\; k\; =\; 0,1,2\}$
Approximability	Нет FPRAS для $k>2\; \{\backslash \; displaystyle\; k>2\; \}$

Вычислительные проблемы, связанные с хроматическим полиномом, включают

• поиск хроматического полинома $P\; (G,\; x)\; \{\backslash \; displaystyle\; P\; (G,\; x)\}$заданного графа G;
• оценка $P\; (G,\; x)\; \{\backslash \; displaystyle\; P\; (G,\; x)\}$в фиксированной точке x для данного G.

Первая проблема более общая, потому что если мы знали коэффициенты $P\; (G,\; x)\; \{\backslash \; displaystyle\; P\; (G,\; x)\}$, мы могли оценить его в любой момент полиномиального времени, потому что степень равна n. Сложность второй тип задач сильно зависит от значения x и имеет n интенсивно изучается в вычислительной сложности. Когда x - натуральное число, эта задача обычно рассматривается как вычисление количества раскрасок по x данного графа. Например, сюда входит задача # 3-раскраска подсчета количества 3-раскрасок, каноническая проблема в изучении сложности подсчета, полная для класса подсчета #P.

Эффективные алгоритмы

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

Известны алгоритмы полиномиального времени для вычисления хроматического полинома для более широких классов графов, включая хордовые графы и графы с ограниченной шириной клики . Последний класс включает кографы и графы с ограниченной древовидной шириной, такие как внешнепланарные графы.

Удаление – сжатие

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

$\varphi \; n\; +\; m\; =\; (1\; +\; 5\; 2)\; n\; +\; m\; \in \; O\; (1,62\; n\; +\; m),\; \{\backslash \; displaystyle\; \backslash \; phi\; ^\; \{n\; +\; m\}\; =\; \backslash \; left\; (\{\backslash \; frac\; \{1\; +\; \{\backslash \; sqrt\; \{5\}\}\}\; \{2\}\}\; \backslash \; right)\; ^\; \{n\; +\; m\}\; \backslash \; in\; O\; \backslash \; left\; (1.62\; ^\; \{n\; +\; m\}\; \backslash \; right),\}$

на графе с n вершинами и m ребрами. Анализ может быть улучшен с точностью до полиномиального множителя числа $t\; (G)\; \{\backslash \; displaystyle\; t\; (G)\}$из остовных деревьев входного графа. На практике, чтобы избежать некоторых рекурсивных вызовов, используются стратегии ветвей и границ и отказ от изоморфизма графов, время выполнения зависит от эвристики, используемой для выбора пары вершин.

Метод куба

Существует естественная геометрическая перспектива раскраски графа, если заметить, что при присвоении натуральных чисел каждой вершине раскраска графа является вектором в целочисленной решетке. Поскольку двум вершинам $i\; \{\backslash \; displaystyle\; i\}$и $j\; \{\backslash \; displaystyle\; j\}$задан один и тот же цвет, это эквивалентно $i\; \{\backslash \; displaystyle\; i\}$'-я и $j\; \{\backslash \; displaystyle\; j\}$' -я координаты в векторе раскраски равны, каждое ребро может быть связано с гиперплоскостью вида $\{x\; \in \; R\; d:\; xi\; =\; xj\}\; \{\backslash \; displaystyle\; \backslash \; \{x\; \backslash \; in\; R\; ^\; \{d\}:\; x\_\; \{i\}\; =\; x\_\; \{j\}\; \backslash \}\}$. Набор таких гиперплоскостей для данного графа называется его графическим расположением. Правильная раскраска графа - это те точки решетки, которые избегают запрещенных гиперплоскостей. Ограничивая набором цветов $k\; \{\backslash \; displaystyle\; k\}$, точки решетки содержатся в кубе $[0,\; k]\; n\; \{\backslash \; displaystyle\; [0,\; k]\; ^\; \{n\; \}\}$. В этом контексте хроматический полином подсчитывает количество точек решетки в $[0,\; k]\; \{\backslash \; displaystyle\; [0,\; k]\}$-куб, которые избегают графического расположения.

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

Задача вычисления количества трехцветных раскрасок данного графа является каноническим примером #P -полной задачи, поэтому проблема вычисление коэффициентов хроматического полинома является # P-трудным. Аналогичным образом, оценка $P\; (G,\; 3)\; \{\backslash \; displaystyle\; P\; (G,\; 3)\}$для данного G является # P-завершенной. С другой стороны, для $k\; =\; 0,\; 1,\; 2\; \{\backslash \; displaystyle\; k\; =\; 0,1,2\}$легко вычислить $P\; (G,\; k)\; \{\backslash \; displaystyle\; P\; (G,\; k)\}$, поэтому соответствующие задачи вычислимы за полиномиальное время. Для целых чисел $k>3\; \{\backslash \; displaystyle\; k>3\}$проблема заключается в # P-hard, который устанавливается аналогично случаю $k\; =\; 3\; \{\backslash \; displaystyle\; k\; =\; 3\}$. Фактически, известно, что $P\; (G,\; x)\; \{\backslash \; displaystyle\; P\; (G,\; x)\}$является # P-сложным для всех x (включая отрицательные целые и даже все комплексные числа), кроме три «легких точки». Таким образом, с точки зрения жесткости # P, сложность вычисления хроматического полинома полностью понятна.

В разложении

$P\; (G,\; x)\; =\; a\; 1\; Икс\; +\; А\; 2\; Икс\; 2\; +\; \cdots \; +\; тревога,\; \{\backslash \; Displaystyle\; P\; (G,\; x)\; =\; a\_\; \{1\}\; x\; +\; a\_\; \{2\}\; x\; ^\; \{2\}\; +\; \backslash \; dots\; +\; a\_\; \{n\}\; x\; ^\; \{n\},\; \}$

коэффициент $an\; \{\backslash \; displaystyle\; a\_\; \{n\}\}$всегда равен 1, и некоторые другие свойства коэффициентов известны. Это вызывает вопрос, являются ли некоторые из коэффициентов легко вычислить. Однако вычисление Вся проблема вычисления a r для фиксированного r ≥ 1 и данного графа G является # P-сложной даже для двудольных плоских графов.

Нет алгоритмов аппроксимации для вычисления $P\; (G,\; x)\; \{\backslash \; displaystyle\; P\; (G,\; x)\}$известны для любого x, кроме трех простых точек. В целочисленных точках $k\; =\; 3,\; 4,\dots \; \{\backslash \; displaystyle\; k\; =\; 3,4,\; \backslash \; dots\}$соответствующая задача принятия решения о том, может ли данный граф быть k-цветным - это NP-hard. Такие задачи не могут быть приближены к любому мультипликативному коэффициенту вероятностным алгоритмом с ограниченной ошибкой, если NP = RP, потому что любое мультипликативное приближение будет различать значения 0 и 1, эффективно решая версию решения за вероятностное полиномиальное время с ограниченной ошибкой. В частности, при том же предположении это исключает возможность полностью полиномиальной схемы рандомизированной аппроксимации (FPRAS). По другим пунктам нужны более сложные аргументы, и этот вопрос находится в центре активных исследований. По состоянию на 2008 год известно, что не существует FPRAS для вычисления $P\; (G,\; x)\; \{\backslash \; displaystyle\; P\; (G,\; x)\}$для любого x>2, кроме случаев, когда NP = RP держит.

• Вайсштейн, Эрик У. «Хроматический многочлен». MathWorld.
• PlanetMath Хроматический полином
• Код для вычисления Тутте, Хроматического полинома и полинома потока Гэри Хаггарда, Дэвида Дж. Пирса и Гордона Ройла: [1]