WikiSort.ru - Не сортированное

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

Треугольник ${\displaystyle K_{3}}$	${\displaystyle t(t-1)(t-2)}$
Полный граф ${\displaystyle K_{n}}$	${\displaystyle t(t-1)(t-2)...(t-(n-1))}$
Дерево с ${\displaystyle n}$ вершинами	${\displaystyle t(t-1)^{n-1}}$
Цикл ${\displaystyle C_{n}}$	${\displaystyle (t-1)^{n}+(-1)^{n}(t-1)}$
Граф Петерсена	${\displaystyle t(t-1)(t-2)(t^{7}-12t^{6}+67t^{5}-230t^{4}+529t^{3}-814t^{2}+775t-352)}$

Нахождение хроматического многочлена произвольного графа

Для графа-вершины хроматический многочлен равен ${\displaystyle t}$

${\displaystyle |V(G)|=1\Rightarrow P(G,t)=t.}$

Хроматический многочлен графа равен произведению хроматических многочленов его компонент

${\displaystyle G_{1}\cap G_{2}=\emptyset \Rightarrow P((G_{1}\cup G_{2}),t)=P(G_{1},t)P(G_{2},t).}$

Также существует рекуррентное соотношение — теорема Зыкова^[3], так называемая формула удаления и стягивания

${\displaystyle P(G,t)=P(G-(u,v),t)-P(G/(u,v),t),}$

где ${\displaystyle u}$ и ${\displaystyle v}$  — смежные вершины, ${\displaystyle G-(u,v)}$  — граф, получающийся из графа ${\displaystyle G}$ путём удаления ребра ${\displaystyle (u,v),}$ а ${\displaystyle G/(u,v)}$  — граф, получающийся из графа ${\displaystyle G}$ путём стягивания ребра ${\displaystyle (u,v)}$ в точку.
Можно использовать эквивалентную формулу

${\displaystyle P(G,t)=P(G+(u,v),t)+P(G/(u,v),t),}$

где ${\displaystyle u}$ и ${\displaystyle v}$  — несмежные вершины, а ${\displaystyle G+(u,v)}$  — граф, получающийся из графа ${\displaystyle G}$ путём добавления ребра ${\displaystyle (u,v).}$

Свойства хроматического многочлена

Для всех целых положительных ${\displaystyle t}$

${\displaystyle P(G,t)\geq 0.}$

Хроматическое число ${\displaystyle \chi (G)}$  — наименьшее целое положительное ${\displaystyle t}$ , для которого

${\displaystyle P(G,t)>0.}$

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

${\displaystyle \deg P(G,t)=|V(G)|}$