Хроматический полином Лемма. Хроматический полином графа имеет вид P(G,x) = P(G1,x) +P(G2,x), где G1 - граф, полученный из G добавлением нового ребра (uv), а граф G2 получается из G отождествлением вершин u и v. Задача. Найти хроматический полином графа Решение Способ 1 Воспользуемся леммой, записанной в виде P(G1,x) = P(G,x) - P(G2,x) Убирая ребра и отождествляя соответствующие вершины, сведем исходный граф к пустым графам. Известно, что для пустого графа P(On,x)=xn. G = G1- G2 = O4- O3 - 2(O3 - O2)-(O3- O2 - 2(O2 - O1))=O4- 4O3 + 5O2 - 2O1. P(G,x) = x4-4x3+5x2-2x Способ 2. Хроматическая редукция Добавляя ребра и отождествляя соответствующие вершины, получим полные графы. Известно, что для полного графа хроматический полином равен факториальной степени переменной P(On,x)=x(n). P(G,x) = x(4)+2x(3) = x(x-1)(x-2)(x-3) + 2 x(x-1)(x-2) = x4-4x3+5x2-2x Заметим, что x(n)= n е k=0  s1(n,k)xk, где s1(n,k) - числа Стирлинга первого рода. xn= n е k=0  s2(n,k)x(k), где s2(n,k) - числа Стирлинга второго рода, обладающие следующими свойствами s2(n,k) = s2(n-1,k-1)+ks2(n-1,k),  0 < k < n, s2(n,n) = 1,   (n і 0), s2(n,0)=0,   (n > 0)

Литература.

Асанов М., Баранский В., Расин В. Дискретная математика. Графы, матроиды, алгоритмы. РХД 2001.

Кирсанов М.Н. Графы в Maple с.16-21 - М.:ФИЗМАТЛИТ, 2007.