Просмотр кода страницы Хроматический многочлен

[[Файл:Chromatic polynomial of all 3-vertex graphs BW.png|thumb|250px|right|Все неизоморфные графы с 3 вершинами и их хроматические многочлены, по часовой стрелке сверху. <br>Независимое 3-множество: <math>k^3</math>. <br>Ребро и одна вершина: <math>k^2(k-1)</math>. <br>3-путь: <math>k(k-1)^2</math>. <br>3-клика: <math>k(k-1)(k-2)</math>.]]

'''Хроматический многочлен''' — [[многочлен]], изучаемый в [[Алгебраическая теория графов|алгебраической теории графов]], представляющий число [[Раскраска графов|раскрасок графа]] как функцию от числа цветов. Первоначально определён [[Биркгоф, Джордж Дейвид|Джорджем Биркгофов]] для попытки решения на [[Проблема четырёх красок|проблемы четырёх красок]]. Обобщен и систематически изучен [[Уитни, Хасслер|Хасслером Уитни]], [[Татт, Уильям Томас|Татт]] обобщил хроматический многочлен до [[Многочлен Татта|многочлена Татта]], связав его с {{не переведено 5|Модель Поттса|моделью Поттса||Potts model}} [[Статистическая физика|статистической физики]].

== История ==
[[Биркгоф, Джордж Дейвид|Джордж Биркгоф]] ввёл хроматический многочлен в 1912 году, определяя его только для [[Планарный граф|планарных графов]] в попытке доказать [[Проблема четырёх красок|теорему о четырёх красках]]. Если <math>P(G, k)</math> обозначает число правильных раскрасок графа ''G'' ''k'' цветами, то можно было бы доказать теорему о четырёх красках, показав, что <math>P(G, 4)>0</math> для всех планарных графов ''G''. Таким образом он надеялся использовать мощь математического анализа и алгебры для изучения корней многочленов для изучения комбинаторной задачи раскраски.

[[Уитни, Хасслер|Хасслер Уитни]] обобщил многочлен Биркгофа с планарного случая на графы общего вида в 1932. В 1968 году Рид поднял вопрос: какие многочлены являются хроматическими многочленами для некоторых графов (задача остаётся открытой), и ввёл понятие хроматически эквивалентных графов. В настоящее время хроматические многочлены являются центральными объектами [[Алгебраическая теория графов|алгебраической теории графов]]{{sfn|Biggs|1993|с=Некоторые главы}}.

== Определение ==
[[Файл:Chromatic polynomial of all 3-vertex graphs BW with colorings.png|thumb|300px|right|Все правильные раскраски графов с 3 вершинами при использовании ''k''цветов (<math>k=0,1,2,3</math>). Хроматический многочлен каждого графа интерполирует число правильных раскрасок.]]

Хроматический многочлен графа ''G'' считает число правильных [[Раскраска графов|раскрасок вершин]]. Обычно многочлен обозначается как <math>P_G(k)</math>, <math>\chi_G(k)</math>, <math>\pi_G(k)</math> или <math>P(G, k)</math>. Последнее обозначение будем использовать в остальной части статьи.

Например, [[Путь (теория графов)|путь]] <math>P_3</math> с 3 вершинами не может быть раскрашен в 0 цветов или 1 цветом. Используя 2 цвета граф можно раскрасить двумя способами. Используя 3 цвета граф можно раскрасить 12 способами.
{| class="wikitable"
|-
|Доступно цветов <math>k</math> || 0 || 1 || 2 || 3
|-
|Число раскрасок <math>P(P_3, k)</math> || 0 || 0 || 2 || 12
|}

Для графа ''G'' с ''n'' вершинами хроматический многочлен определяется как уникальный [[Интерполяция алгебраическими многочленами|интерполирующий многочлен]] степени, не превосходящей ''n'', проходящий через точки

: <math>\left \{ (0, P(G, 0)), (1, P(G, 1)), \cdots, (n, P(G, n)) \right \}.</math>

Если граф ''G'' не содержит вершин с петлями, то хроматический многочлен является [[Приведённый многочлен|приведённым многочленом]] степени в точности ''n''. Фактически, для приведённого выше примера мы имеем

: <math>P(P_3, t)= t(t-1)^2, \qquad P(P_3, 3)=12.</math>

Хроматический многочлен включает по меньшей мере столько информации о раскрашиваемости графа ''G'', сколько содержится в хроматическом числе. Более того, хроматическое число является наименьшим положительным целым, при котором хроматический многочлен не обращается в нуль,
: <math>\chi (G)=\min\{ k : P(G, k) > 0 \}.</math>

== Примеры ==
{| class="wikitable"
|+Хроматические многочлены для некоторых графов
|-
| Треугольник <math>K_3</math> || <math>t(t-1)(t-2)</math>
|-
| [[Полный граф]] <math>K_n</math> || <math>t(t-1)(t-2)\cdots(t-(n-1))</math>
|-
| [[Путь (теория графов)|Путь]] <math>P_n</math> || <math>t(t-1)^{n-1}</math>
|-
| Любое [[Дерево (теория графов)|дерево]] с ''n'' вершинами || <math>t(t-1)^{n-1}</math>
|-
| [[Граф-цикл|Цикл]] <math>C_n</math>|| <math>(t-1)^n+(-1)^n(t-1)</math>
|-
| [[Граф Петерсена]] || <math>t(t-1)(t-2) \left (t^7-12t^6+67t^5-230t^4+529t^3-814t^2+775t-352 \right)</math>
|}

== Свойства ==
Для фиксированного графа ''G'' с ''n'' вершинами хроматический многочлен <math>P(G, t)</math> является, фактически, многочленом степени ''n''. По определению, вычисление значения многочлена <math>P(G, k)</math> даёт число ''k''-раскрасок графа ''G'' для <math>k=0, 1,\cdots, n</math>. То же самое верно для ''k'' > ''n''.

Выражение
: <math>(-1)^{|V(G)|} P(G,-1)</math>
даёт число [[Направленный ациклический граф|ациклических ориентаций]] графа ''G''{{sfn|Stanley|1973}}.

Значение производной от многочлена в точке 1, <math>P'(G, 1)</math> равно с точностью до знака хроматическому инварианту <math>\theta(G)</math>.
 
Если граф ''G'' имеет ''n'' вершин, ''m'' рёбер и ''c'' [[Компонента связности графа|компонент]] <math>G_1, \cdots, G_c</math>, то
* Коэффициенты при <math> t^0, \cdots, t^{c-1}</math> равны нулю.
* Коэффициенты при <math> t^c, \cdots, t^n</math> все ненулевые.
* Коэффициент при <math>t^n</math> в <math>P(G, t)</math> равен 1.
* Коэффициент при <math>t^{n-1}</math> в <math>P(G, t)</math> равен <math>-m</math>.
* Коэффициенты любого хроматического многочлена знакопеременны.
* Абсолютные значения коэффициентов любого хроматического многочлена образует {{не переведено 5|Логарифмически вогнутая последовательность|логарифмически вогнутую последовательность||Logarithmically concave sequence}}{{sfn|Huh|2012}}.
* <math>P(G, t) = P(G_1, t)P(G_2,t) \cdots P(G_c,t)</math>

Граф ''G'' с ''n'' вершинами является деревом тогда и только тогда, когда
: <math>P(G, t) = t(t-1)^{n-1}.</math>

=== Хроматическая эквивалентность ===
[[Файл:Chromatically equivalent graphs.svg|thumb|right|250px|<center>Три графа с хроматическим многочленом, равным <math>(x-2)(x-1)^3x</math>.</center>]]

Говорят, что два графа хроматически эквивалентны, если они имеют одинаковые хроматические многочлены. Изоморфные графы имеют одинаковые хроматические многочлены, но неизоморфные графы могут быть хроматически эквивалентными. Например, все деревья с ''n'' вершинами имеют одинаковые хроматические многочлены:
: <math>(x-1)^{n-1}x,</math>
В частности,
: <math>(x-1)^3x</math>
является хроматическим многочленом как для [[Граф-звезда|клешни]], так и для [[Путь (теория графов)|пути]] с 4 вершинами.

=== Хроматическая единственность ===
Граф является хроматически уникальным, если он определяется хроматическим многочленом с точностью до изоморфизма. Другими словами, если граф ''G'' хроматически уникален, то из <math>P(G, t) = P(H, t)</math> следует, что ''G'' и ''H'' изоморфны.

Все [[Граф-цикл|циклы]] хроматически уникальны{{sfn|Chao, Whitehead|1978}}.

=== Хроматические корни ===
[[Нуль функции|Корень]] (или ''нуль'') хроматического многочлена (называется «хроматическим корнем») — это значение ''x'', для которого <math>P(G, x)=0</math>. Хроматические корни хорошо изучены. Фактически, исходным побуждением Биркгофа для введения хроматического многочлена было показать, что для планарных графов <math>P(G, x)>0</math> для ''x'' ≥ 4. Это доказало бы [[Проблема четырёх красок|теорему о четырёх красках]].

Никакой граф нельзя раскрасить в 0 цветов, так что 0 всегда является хроматическим корнем. Только графы без рёбер могут быть раскрашены в один цвет, так что 1 является хроматическим корнем любого графа, имеющего по меньшей мере одно ребро. С другой стороны, за исключением этих двух случаев, никакой граф не может иметь в качестве хроматического корня вещественное число, меньшее либо равное 32/27{{sfn|Jackson|1993}}. Результат Татта связывает [[золотое сечение]] <math>\phi</math> с изучением хроматических корней, показывая, что хроматические корни существуют очень близко к <math>\phi^2</math> — если <math>G_n</math> является планарной триангуляцией сферы, то

: <math>P(G_n,\phi^2) \leq \phi^{5-n}.</math>

В то время как вещественная прямая, таким образом, имеет большие куски, которые не содержат хроматических корней ни для какого графа, любая точка на [[Комплексная плоскость|комплексной плоскости]] произвольно близка к хроматическому корню в том смысле, что существует бесконечное семейство графов, хроматические корни которых плотны на комплексной плоскости{{sfn|Sokal|2004}}.

=== Категоризация ===
Хроматический многочлен [[Категоризация|категоризирован]] с помощью теории гомологий, близко связанной с {{не переведено 5|Гомология Хованова|гомологией Хованова||Khovanov homology}}{{sfn|Helme-Guizon, Rong|2005}}.

== Алгоритмы ==
{{Карточка
|вверху            = Хроматический многочлен
|стиль_вверху      = background: #DD9; font-size: 125%;
|стиль_меток       = font-weight:normal
|метка1     = Вход
|текст1     = Граф ''G'' с ''n'' вершинами.
|метка2     = Выход
|текст2     = Коэффициенты <math>P(G, t)</math>
|метка3     = Время работы
|текст3     = <math>O(2^nn^r)</math> для некоторой константы  <math>r</math>
|метка4     = Сложность
|текст4     = [[Класс Sharp-P|#P]]-трудна
|метка5     = Сводится из
|текст5     = <nowiki>#</nowiki>3SAT
|
}}
{{Карточка
|вверху            = <nowiki>#</nowiki>k-раскраски
|стиль_вверху      = background: #DD9; font-size: 125%;
|стиль_меток       = font-weight:normal
|метка1     = Вход
|текст1     = Граф ''G'' с ''n'' вершинами.
|метка2     = Выход
|текст2     = <math>P(G, k)</math>
|метка3     = Время работы
|текст3     = Принадлежит [[Класс P|P]] для <math>k=0,1,2</math>. <math>O(1{,}6262^n)</math> для   <math>k=3</math>. В противном случае
<math>O(2^nn^r)</math> для некоторой константы <math>r</math>
|метка4     = Сложность
|текст4     = [[Класс Sharp-P|#P]]-трудна пока
<math>k=0,1,2</math>
|метка5     = Approximability
|текст5     = No FPRAS for <math>k>2</math>
|
}}

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

* нахождение хроматического многочлена <math>P(G, t)</math> для данного графа ''G'';
* вычисление <math>P(G, k)</math> в фиксированной точке ''k'' для данного графа ''G''.

Первая задача более общая, поскольку, зная коэффициенты <math>P(G, t)</math>, мы можем вычислить значение многочлена в любой точке за полиномиальное время. [[Вычислительная сложность]] второй задачи сильно зависит от величины ''k''. Когда ''k'' является натуральным числом, задачу можно рассматривать как вычисление количества ''k''-раскрасок данного графа. Например, задача включает подсчёт '''3-раскрасок''' в качестве канонической задачи для изучения сложности подсчёта. Эта задача является полной в классе [[Класс Sharp-P|#P]].

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

Известны алгоритмы полиномиального времени для вычисления хроматического многочлена для широкого класса графов, в который входят [[Хордальный граф|хордальные графы]]{{sfn|Naor, Naor, Schaffer|1987}} и графы с ограниченной [[Кликовая ширина|кликовой шириной]]{{sfn|Giménez, Hliněný, Noy|2005}}{{sfn|Makowsky, Rotics, Averbouch, Godlin|2006}}. Второй из этих классов, в свою очередь, включает [[кограф]]ы и графы с ограниченной [[Древесная ширина (теория графов)|древесной шириной]], такие как [[Внешнепланарный граф|внешнепланарные графы]].

В интернете присутствуют лица, пытающиеся решить задачу коллективно, и им помогают активные автономные помощники, особенно для хроматических многочленов высокой степени{{sfn|Shirado, Christakis|2017|с=370–374 }}.

=== Удаление — стягивание ===
Рекурсивный способ вычисления хроматического многочлена базируется на [[Стягивание ребра|стягивании ребра]] — для пары вершин <math>u</math> и <math>v</math> граф <math>G/uv</math> получается путём слияния двух вершин и удаления ребра между ними. Хроматический многочлен удовлетворяет рекурсивному соотношению
: <math>P(G,k)=P(G-uv, k)- P(G/uv,k)</math>,
где <math>u</math> и <math>v</math> являются смежными вершинами и <math>G-uv</math> является графом с удалённым ребром <math>uv</math>. Эквивалентно,
: <math>P(G,k)= P(G+uv, k) + P(G/uv,k)</math>
если <math>u</math> и <math>v</math> не смежны и <math>G+uv</math> является графом с добавленным ребром <math>uv</math>. В первой форме рекурсия прекращается на наборе пустых графов. Эти рекуррентные отношения называются также ''фундаментальной теоремой редукции''{{sfn|Dong, Koh, Teo|2005}}. Вопрос [[Татт, Уильям Томас|Татта]] о том, какие другие свойства графа удовлетворяют тем же рекуррентным соотношениям, привёл к открытию обобщения хроматического многочлена на две переменные — [[Многочлен Татта|многочлену Татта]].

Выражения дают рекурсивную процедуру, называемую ''алгоритмом удаления — стягивания'', которая является базисом многих алгоритмов раскраски графов. Функция ''ChromaticPolynomial'' в системе компьютерной алгебры [[Mathematica]] использует вторую рекуррентную формулу если граф плотный, и первую, если граф разреженный{{sfn|Pemmaraju, Skiena|2003}}. Худшее время работы для обоих формул удовлетворяет рекуррентному соотношению для [[Числа Фибоначчи|чисел Фибоначчи]], так что в худшем случае алгоритм работает за время (с точностью до некоторого полиномиального коэффициента)

: <math>\phi^{n+m}=\left (\frac{1+\sqrt{5}}{2} \right)^{n+m}\in O\left(1{,}62^{n+m}\right)</math>

на графе с ''n'' вершинами и ''m'' рёбрами{{sfn|Wilf|1986}}. Анализ времени работы можно улучшить до полиномиального множителя числа <math>t(G)</math> [[Остовное дерево|остовных деревьев]] входного графа{{sfn|Sekine, Imai, Tani|1995}}. На практике используется стратегия [[Метод ветвей и границ|ветвей и границ]] вместе с отбрасыванием [[Изоморфизм|изоморфных графов]], чтобы исключить рекурсивные вызовы, и время зависит от эвристики, используемой при выборе пары вершин (для исключения-стягивания).

=== Метод куба ===
Существует естественный геометрический подход к раскраске графов, если заметить, что при назначении натуральных чисел каждой вершине раскраска графов является вектором целочисленной решётки.
Поскольку присвоение двум вершинам <math>i</math> и <math>j</math> одного цвета эквивалентно равенству координат <math>i</math> и <math>j</math> в векторе раскраски, каждое ребро можно ассоциировать с гиперплоскостью вида <math>\{x\in R^d:x_i=x_j\}</math>. Набор таких гиперплоскостей для данного графа называется его '''графической {{не переведено 5|Конфигурация гиперплоскостей|конфигурацией гиперплоскостей||arrangement of hyperplanes}}'''. Правильная раскраска графа — это раскраска, вектор которой не оказывается на запрещённой плоскости.
Ограниченные множеством цветов <math>k</math>, точки решётки попадают в куб <math>[0,k]^n</math>. В этом контексте хроматический многочлен подсчитывает точки решётки в <math>[0,k]</math>-кубе, которые не попадают на графическую конфигурацию.

=== Вычислительная сложность ===
Задача вычисления числа 3-раскрасок данного графа является каноническим примером [[Класс Sharp-P|#P]]-полной задачи, так что задача вычисления коэффициентов хроматического многочлена #P-трудна. Аналогично, вычисление <math>P(G, 3)</math> для данного графа ''G'' #P-полна. С другой стороны, для <math>k=0,1,2</math> легко вычислить <math>P(G, k)</math>, так что соответствующие задачи имеют полиномиальную по времени трудность. Для целых чисел <math>k>3</math> задача #P-трудна, что устанавливается подобно случаю <math>k=3</math>. Фактически, известно, что <math>P(G, x)</math> #P-трудна для всех ''x'' (включая отрицательные целые числа и даже все комплексные числа), за исключением трёх «простых точек»<ref>Йегер, Вертиган и Уэлш {{harv|Jaeger, Vertigan, Welsh|1990}}, базируясь на сведении Линиала {{harv|Linial|1986}}.</ref>. Таким образом, сложность вычисления хроматического многочлена полностью понятна.

В многочлене

: <math>P(G, t)= a_1 t + a_2t^2+\dots +a_nt^n,</math>

коэффициент <math>a_n</math> всегда равен 1, а также известны некоторые другие свойства коэффициентов. Это поднимает вопрос, нельзя ли вычислить некоторые коэффициенты попроще. Однако задача вычисления ''a<sub>r</sub>'' для фиксированного ''r'' и данного графа ''G'' является #P-трудной{{sfn|Oxley, Welsh|2002}}.

Не известно никакого [[Аппроксимационный алгоритм|аппроксимационного алгоритма]] вычисления <math>P(G, x)</math> для любого ''x'', за исключением трёх простых точек. В целых точках <math>k=3,4,\dots</math> соответствующая [[задача разрешимости]] определения, может ли данный граф быть раскрашен в ''k'' цветов, [[NP-трудная задача|NP-трудна]]. Такие задачи не могут быть аппроскимированы с любым коэффициентом с помощью полиномиального вероятностного алгоритма с ограниченной ошибкой, разве только NP = RP, поскольку любая мультипликативная аппроксимация различала бы значения 0 и 1, что было бы эффективным решением задачи с помощью полиномиального вероятностного алгоритма с ограниченной ошибкой в форме [[Задача разрешимости|задачи разрешимости]]. В частности, при некоторых предположениях, это исключает возможность [[Приближенная схема полиномиального времени|полностью полиномиальной рандомизированной аппроксимационной схемы (FPRAS)]]. Для других точек нужны более сложные рассуждения и вопрос находится в фокусе активных поисков. На 2008 известно, что не существует [[Приближенная схема полиномиального времени|FPRAS-схемы]] для вычиcления <math>P(G, x)</math> для любого ''x'' > 2, разве только [[Класс NP|NP]] = [[Класс RP|RP]]{{sfn|Goldberg, Jerrum|2008}}.

== Примечания ==
{{примечания}}

== Литература ==
* {{статья|автор=А. Ю. Эвнин|заглавие=Хроматический многочлен графа в задачах|ссылка=http://mi.mathnet.ru/mo42 |язык=ru|издание=[[Математическое образование (журнал)|Математическое образование]]|год=2014|том=|номер=4(72)|страницы=9—15|doi=|issn=}}
* {{книга
|автор=Biggs N.
|ref=Biggs
|заглавие=Algebraic Graph Theory
|издательство=Cambridge University Press
|год=1993
|isbn=0-521-45897-8
}}
* {{статья
|автор=Hirokazu Shirado, Nicholas A. Christakis
|ref=Shirado, Christakis
|заглавие=Locally noisy autonomous agents improve global human coordination in network experiments
|ссылка=http://www.nature.com/doifinder/10.1038/nature22332
|издание=Nature
|том=545
|год=2017
|выпуск=7654
|страницы=370–374
|doi=10.1038/nature22332
}}
* {{книга
|автор=Chao C.-Y., Whitehead E. G.
|ref=Chao, Whitehead
|часть=On chromatic equivalence of graphs
|заглавие=Theory and Applications of Graphs
|год=1978
|том=642
|страницы=121–131
|издательство=Springer
|серия=Lecture Notes in Mathematics
|isbn=978-3-540-08666-6
}}
* {{книга
|автор=Dong F. M., Koh K. M., Teo K. L.
|ref=Dong, Koh, Teo
|заглавие=Chromatic polynomials and chromaticity of graphs
|издательство=World Scientific Publishing Company
|год=2005
|isbn= 981-256-317-2
}}
* {{книга
|автор=Giménez O., Hliněný P., Noy M.
|ref=Giménez, Hliněný, Noy
|часть=Computing the Tutte polynomial on graphs of bounded clique-width
|doi=10.1007/11604686_6
|страницы=59–68
|издательство=Springer-Verlag
|серии=Lecture Notes in Computer Science
|заглавие=Proc. 31st Int. Worksh. Graph-Theoretic Concepts in Computer Science (WG 2005)
|том=3787
|год=2005
}}
* {{статья
|автор=Goldberg L.A., Jerrum M.
|ref=Goldberg, Jerrum
|заглавие=Inapproximability of the Tutte polynomial
|издание=Information and Computation
|doi=10.1016/j.ic.2008.04.003    
|год=2008
|том=206
|страницы=908
|выпуск=7
}}
* {{статья
|автор=Laure Helme-Guizon, Yongwu Rong
|ref=Helme-Guizon, Rong
|заглавие=A categorification of the chromatic polynomial
|издание=Algebraic & Geometric Topology
|doi=10.2140/agt.2005.5.1365   
|год=2005
|том=5
|страницы=1365–1388
|выпуск=4
}}
* {{статья
|автор=Huh J.
|ref=Huh
|заглавие=Milnor numbers of projective hypersurfaces and the chromatic polynomial of graphs
|год=2012
|издательство=arXiv:1008.4749v3
}}
* {{статья
|doi= 10.1017/S0963548300000705
|автор=Jackson B.
|ref=Jackson
|заглавие=A Zero-Free Interval for Chromatic Polynomials of Graphs
|издание=Combinatorics, Probability and Computing
|том=2
|страницы=325–336
|год= 1993
}}
* {{статья
|doi=10.1017/S0305004100068936
|автор=Jaeger F., Vertigan D. L., Welsh D. J. A. 
|ref=Jaeger, Vertigan, Welsh 
|заглавие=On the computational complexity of the Jones and Tutte polynomials
|издание=Mathematical Proceedings of the Cambridge Philosophical Society
|том=108
|страницы=35–53
|год=1990
}}
* {{статья
|doi=10.1137/0607036
|автор=Linial N.
|ref=Linial
|заглавие=Hard enumeration problems in geometry and combinatorics
|издание=SIAM J. Algebraic Discrete Methods
|том= 7
|выпуск=2
|страницы=331–335
|год=1986
}}
* {{книга
|автор=Makowsky J. A., Rotics U., Averbouch I., Godlin B.
|ref=Makowsky, Rotics, Averbouch, Godlin
|часть=Computing graph polynomials on graphs of bounded clique-width
|doi=10.1007/11917496_18
|страницы=191–204
|издательство=Springer-Verlag
|серия=Lecture Notes in Computer Science
|заглавие=Proc. 32nd Int. Worksh. Graph-Theoretic Concepts in Computer Science (WG 2006)
|том=4271
|год=2006
}}
* {{книга
|автор=Naor J., Naor M., Schaffer A.
|ref=Naor, Naor, Schaffer
|часть=Fast parallel algorithms for chordal graphs
|doi=10.1145/28395.28433
|страницы=355–364
|заглавие=Proc. 19th ACM Symp. Theory of Computing (STOC '87)
|год=1987
}}
* {{статья
|автор=Oxley J. G., Welsh D. J. A.
|ref=Oxley, Welsh
|заглавие=Chromatic, flow and reliability polynomials: The complexity of their coefficients.
|издание=[[Combinatorics, Probability and Computing]]
|том=11
|год=2002
|выпуск=4
|страницы=403–426
}}
* {{книга
|автор=Pemmaraju S., Skiena S.
|ref=Pemmaraju, Skiena
|заглавие=Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica
|ссылка=https://archive.org/details/computationaldis0000pemm
|издательство=Cambridge University Press
|год=2003
|часть=section 7.4.2
|isbn=0-521-80686-0
}}
* {{книга
|автор=Sekine K., Imai H., Tani S.
|ref=Sekine, Imai, Tani
|часть=Computing the Tutte polynomial of a graph of moderate size
|заглавие=Algorithms and Computation, 6th International Symposium, Lecture Notes in Computer Science 1004
|место= Cairns, Australia, December 4–6, 1995
|издательство=Springer
|год= 1995
|страницы=224–233
}}
* {{статья
|doi=10.1017/S0963548303006023
|автор=Sokal A. D.
|ref=Sokal
|заглавие=Chromatic Roots are Dense in the Whole Complex Plane
|издание=[[Combinatorics, Probability and Computing]]
|год=2004
|страницы=221–261
|том= 13
|выпуск=2 
}}
* {{статья
|doi=10.1016/0012-365X(73)90108-8
|автор=Stanley R. P.
|ref=Stanley
|заглавие=Acyclic orientations of graphs
|издание=[[Discrete Mathematics (journal)|Disc. Math.]] 
|том=5
|страницы=171–178
|год= 1973
|выпуск=2
}}
* {{книга
|автор=Vitaly I. Voloshin 
|ref=Voloshin 
|заглавие=Coloring Mixed Hypergraphs: Theory, Algorithms and Applications. 
|издательство=American Mathematical Society 
|год=2002
|isbn=0-8218-2812-6
}}
* {{книга
|автор=Wilf H. S.
|ref=Wilf
|заглавие=Algorithms and Complexity
|издательство=Prentice–Hall
|год=1986
|isbn= 0-13-021973-8
}}

== Ссылки ==
* {{MathWorld | urlname=ChromaticPolynomial| title=Chromatic polynomial}}
* [[PlanetMath]] [http://planetmath.org/encyclopedia/ChromaticPolynomial.html Chromatic polynomial]
* Code for computing Tutte, Chromatic and Flow Polynomials by Gary Haggard, David J. Pearce and Gordon Royle: [http://www.ecs.vuw.ac.nz/~djp/tutte/]{{Недоступная ссылка|date=июля 2021 |bot=InternetArchiveBot }}
{{rq|checktranslate|style|tex}}

[[Категория:Инварианты графов]]
[[Категория:Раскраска графа]]