Изменения
→Связь с хроматическим многочленом
==Связь с хроматическим многочленом==
{{Теорема
|statement=
Для графа <tex> G </tex> и <tex> k \in N </tex> выполняется соотношение <tex> \chi _G (k) = (-1)^{|V| - c(G)}k^{c(G)}T_G(1 - k, 0) </tex>.
|proof=
Воспользуемся универсальным свойством многочлена Татта для функции <tex> P_G(k) = \frac {\chi _G (k)}{k^{|V|}} </tex>. Проверим условие теоремы. <br>
Пусть ребро <tex> e </tex> является мостом. Тогда множество вершин <tex> V </tex> разбивается на два непересекающихся подмножества: <tex> V_1 </tex> и <tex> V_2 </tex>. Обозначим через <tex> G_1 </tex> и <tex> G_2 </tex> соответствующие подграфы. Их раскраски не связаны друг другом, поэтому <tex> \chi_{G \backslash e} (k) = \chi_{G_1} (k) * \chi_{G_2} (k) </tex>. Далее, правильная раскраска <tex> G/e </tex> получается из правильных раскрасок <tex> G_1 </tex> и <tex> G_2 </tex>, где цвета склеиваемых вершин совпадают. Можно взять любую правильную раскраску <tex> G_1 </tex>, для чего есть <tex> \chi_{G_1} (k) </tex>, а из правильных раскрасок <tex> G_2 </tex> годится только доля <tex> \frac {1}{k} </tex>, где цвет склеиваемой вершины нужный. Таким образом, <tex> \chi _{G/e}(k) = \frac {1}{k} \chi _{G_1}(k) \chi _{G_2}(k) </tex>. Далее, по рекуррентному свойству хроматического многочлена <tex> \chi _{G}(k) = \chi _{G \backslash e}(k) - \chi _{G / e}(k) = (1 - \frac {1}{k})\chi _{G_1}(k)*\chi _{G_2}(k) = (k - 1)\chi _{G / e}(k) </tex>. Значит, <tex> P_G (k) = \frac {\chi _{G}(k)}{k^{|V|}} = \frac {(k - 1)\chi _{G / e}(k)}{k^{|V|}} = \frac {k - 1}{k} P_{G / e} (k) </tex>, то есть первое условие выполнено для <tex> x_0 = \frac {k - 1}{k} </tex>. <br>
Пусть ребро <tex> e </tex> является петлёй. Тогда правильных раскрасок нет, то есть <tex> P_G (k) = 0 </tex>. Значит второе условие выполнено для <tex> y_0 = 0 </tex>.
Пусть ребро <tex> e </tex> не является ни мостом, ни петлёй. Опять же, в силу рекуррентного свойства хроматического многочлена <tex> \chi _{G}(k) = \chi _{G \backslash e}(k) + \chi _{G / e}(k) </tex>. Поделив на <tex> k^{|V|} </tex>, получим <tex> P_G(k) = -\frac {1}{k} P_{G / e} (k) + P_{G \backslash e} (k) </tex>. Значит, третье соотношение выполнено для <tex> a = \frac {1}{k}, b = 1 </tex>. <br>
Согласно универсальному свойству многочлена Татта получаем <tex> P_G (k) = (-\frac {1}{k})^{\rho (E)} T_G(1 - k, 0) </tex>. Значит, <tex> \chi _G (k) = (-1)^{\rho (E)}k^{|V| - \rho (E)}T_G(1 - k, 0) </tex>. Поскольку <tex> \rho (E) = |V| - c(G) </tex>, получаем <tex> \chi _G (k) = (-1)^{|V| - c(G)}k^{c(G)}T_G(1 - k, 0) </tex>.
}}
==Значение многочлена Татта для некоторых значений переменных==
