Формула Зыкова

Эта статья находится в разработке!

Определение:

Независимым множеством (кокликой, англ. coclique) в графе [math]G[/math] называется непустое [math]S \subset VG: \forall v,u \in S\[/math] ребро [math](v,u) \notin EG[/math].

Теорема (Зыкова):

Хроматический многочлен графа [math]G[/math] [math]p(G,x)=\sum\limits_{i=1}^n pt(G,i)x^{\underline{i}}[/math], где [math]pt(G,i)[/math] — число способов разбить вершины [math]G[/math] на [math]i[/math] независимых множеств.

Литература

1. Асанов М. О., Баранский В. А., Расин В. В. Дискретная математика: Графы, матроиды, алгоритмы. — Ижевск: НИЦ «РХД», 2001. — С. 140—141. — ISBN 5-93972-076-5