Хроматический многочлен

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

Хроматический многочлен полного графа

, так как первую вершину полного графа [math]K_{n}[/math] можно окрасить в любой из [math]x[/math] цветов, вторую - в любой из оставшихся [math]x-1[/math] цветов и т. д. Очевидно, что если [math]x[/math] меньше [math]n[/math], то и многочлен равен [math]0[/math], потому что один из его множителей [math]0[/math].
Примечание. В некоторых источниках [math]x^{\underline{n}}[/math] ([math]x[/math] в [math]n[/math]-убывающей) обозначают [math]x^{(n)}[/math]. Это не очень удобно, так как легко спутать с [math]n[/math]-ой производной.

Хроматический многочлен пустого графа

[math]P(O_{n},x)=x^{n}[/math], так как каждую из [math]n[/math] вершин нулевого графа [math]O_{n}[/math] можно независимо окрасить в любой из [math]x[/math] цветов.
Примечание. Нулевой граф [math]O_{n}[/math] также можно обозначать [math]\overline{K_{n}}[/math] (дополнительный граф для полного графа [math]K_{n}[/math]).