16. Хроматический многочлен, его нахождение и свойства.

Определение. Графом G называется пара (V, E), где – непустое множество вершин графа, а– множество ребер графа, причем каждое ребро – это неупорядоченная пара различных вершин.

Определение. Говорят, что вершины графа G правильно раскрашены с помощью цветов {c₁, c₂,…, c_r}, если каждой вершине поставлен в соответствие некоторый цвет, причем любым двум смежным вершинам соответствуют разные цвета.

Определение. Хроматическим числом графа называется минимальное число красок, достаточное для правильной раскраски его вершин.

Определение. Хроматическим многочленом графа G называется многочлен P(G,x), который при каждом целом неотрицательном значении х равен количеству различных способов правильной раскраски вершин графа G с использованием не более х фиксированных цветов.

Хроматический многочлен легко получить для нулевого и для полного n-вершинного графа. Действительно, P(О_n,x) = хⁿ, поскольку каждую вершину можно покрасить любым из х цветов, независимо от остальных вершин, и все эти раскраски будут правильными. Для полного графа P(K_n,x) = x(x – 1)(x – 2)…(x – n + 1), так как первую вершину можно покрасить любым их х цветов, вторую – любым из х – 1 цветов, третью – любым из х – 2 цветов и т.д.

Утверждение 1. Пусть T_n – произвольное n-вершинное дерево. Тогда P(T_n,x) = x(x – 1)^n – 1.

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

Утверждение 2. Пусть u и v - несмежные вершины графа G, граф получен путем добавления ребра[u,v] в графе G, а граф – отождествлением вершинu и v в графе G. Тогда выполняется тождество P(G, x) = P(,x) + P(,x).

Хроматический многочлен графа содержит некоторую дополни­тельную информацию о самом графе. А именно:

• степень хроматического многочлена равна числу вершин;

• если степень хроматического многочлена равна n, то коэффициент при хⁿ равен 1, а коэффициент при х^n – 1 равен (– m), где m – количество ребер в графе G;

• знаки коэффициентов хроматического многочлена череду­ются;

• хроматическое число графа на единицу больше максимального корня его хроматического многочлена;

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