322
правки
Изменения
→Рекуррентные формулы для хроматических многочленов
{{Теорема
|statement=
Пусть <tex>u</tex> и <tex>v</tex> - несмежные вершины графа <tex>G</tex>. Если <tex>G_1=G\cup(u,v)uv</tex>, а <tex>G_2=G/(u,v)uv</tex> , то <tex>P(G,x)=P(G_1,x)+P(G_2,x)</tex>.
|proof=
Рассмотрим все произвольные раскраски графа <tex>G</tex>. Рассмотрим те из них, при которых вершины <tex>u</tex> и <tex>v</tex> окрашены в разные цвета. Если добавить к графу <tex>G</tex> ребро <tex>(u,v)uv</tex>, то они не изменятся, то есть останутся правильными. Рассмотрим раскраски, при которых <tex>u</tex> и <tex>v</tex> одного цвета. Все эти раскраски останутся правильными и для графа, полученного из <tex>G</tex> слиянием вершин <tex>u</tex> и <tex>v</tex>.
}}
'''Замечание:'''
{{Теорема
|statement=
Пусть <tex>u</tex> и <tex>v</tex> - смежные вершины графа <tex>G</tex>. Если <tex>G_1=G\backslash(u,v)uv</tex> и <tex>G_2=G/(u,v)uv</tex>, то <tex>P(G,x)=P(G_1,x)-P(G_2,x)</tex>.
|proof=
Следует из предыдущей теоремы.
