Теорема

Простой граф G –() раскрашиваемый (- максимальная степень в графе G)

Очевидно, что Х = () для полных графов и циклов нечётные длины. Для остальных графов Х

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

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

Хроматические полиномы Р(G,) имеют значения для каждого целого , равное числу различных правильных раскрасок графа G. ()

Раскрасим любым цветом из в один из оставшихся -1 цветов. Для каждой раскраски существует -1 различных способов раскраски вершин С.

Итак, граф () можно раскрасить различными способами, то хроматический полином графа равен

Хроматический полином пути на n вершинах равен

Пример. Рассмотрим граф c вершинами V1,V2,V3…….При наличии цветов V1- в любой из них , V2--1, V3 --2 и т.д.

Путь U и V – несмежные вершины G.

Пусть е(U,V) ; Если G* е- простой граф, получен из G замыканием вершин U и V и заменой получившегося множества параллельных рёбер на 1 ребро, а G+е – граф полученный добавлением к G ребра е то Р(G,)= Р(G+е, )+Р(G* е, )