查看“︁色多项式”︁的源代码

{{refimprove|time=2015-03-07T03:41:01+00:00}}
在[[代数图论]]中，'''色多项式'''是[[乔治·戴维·伯克霍夫]]为了尝试证明[[四色定理]]而定义的一种[[多项式]]。

'''色多项式'''<math>P(G,t)</math>的值是在[[图]]<math>G</math>中[[顶点 (图论)|顶点]]的不同的<math>t</math>-着色数目，是关于<math>t</math>的多项式。

例如当图<math>G</math>为一点时，<math>P(G,t)=t</math>。

==例子==
{| class="wikitable" 
|+特殊图的色多项式
|-
| [[完全图]]<math>K_n</math> || <math>t(t-1)(t-2)\cdots(t-(n-1))</math>
|-
| [[树 (图论)|树]]<math>T_n</math> || <math>t(t-1)^{n-1}</math>   
|-
| 环<math>C_n</math> || <math>(t-1)^n+(-1)^n(t-1)</math>
|-
| [[佩特森圖]] || <math>t(t-1)(t-2) \left (t^7-12t^6+67t^5-230t^4+529t^3-814t^2+775t-352 \right)</math>
|}

==性质==
给定<math>n</math>阶图<math>G</math>，色多项式<math>P(G, t)</math>是关于<math>t</math>的多项式，且满足以下性质<ref>{{Citation |last=Whitney|first=Hassler|title=The coloring of graphs|journal=Annals of Mathematics|pages=688-718|year=1932|publisher=JSTOR}}</ref>：
* 多项式<math>P(G, t)</math>的次数为<math>n</math>。
* <math>t^n</math>的系数为1。
* <math>t^{n-1}</math>的系数为<math>-|E(G)|</math>。
* <math>t^c,\dots,t^n</math>的系数不为0且正负交替出现。
特别的，设<math>G</math>有<math>c</math>个连通分量，分别为<math>G_1,\dots,G_c</math>，那么
* <math>t^0,\dots,t^{c-1}</math>的系数为0。
* <math>P(G)=\prod_{k=1}^n P(G_k)</math>
===递推公式===
[[File:Edge_contraction_with_multiple_edges.svg|thumb|280px|对于边uv的边收缩（G / {uv}）示意图。]]
给定图<math>G</math>与<math>e\in E(G)</math>，那么
:<math>P(G,k)=P(G-e,k)-P(G/e,k)</math>
其中<math>G/e</math>代表[[边收缩]]：令<math>e</math>所连接的两个顶点计为<math>u</math>和<math>v</math>，而边收缩会使顶点<math>u</math>和<math>v</math>合并成一个新的顶点<math>w</math>，并使原本与<math>u</math>和<math>v</math>相连的所有边都连到<math>w</math>。

'''证明'''<ref>{{Citation|last1=Harris|first1=John|last2=Hirst|first2=Jeffry L.|last3=Mossinghoff|first3=Michael|title=Combinatorics and Graph Theory|year=2008|pages=98–99|publisher=Springer-Verlag New York|series=Undergraduate Texts in Mathematics|isbn=978-0-387-79711-3|doi=10.1007/978-0-387-79711-3}}</ref> 假设<math>e</math>所连接的两个顶点为<math>u</math>和<math>v</math>，考虑图<math>G-e</math>。
* 当<math>u</math>和<math>v</math>的颜色相同时，这种着色方式也是<math>G/e</math>的一种合理着色方式，反之亦然。所以对图<math>G-e</math>将<math>u</math>和<math>v</math>染上相同颜色的着色方式有<math>P(G/e,k)</math>种。
* 当<math>u</math>和<math>v</math>的颜色不同时，这种着色方式也是<math>G</math>的一种合理着色方式，反之亦然。所以对图<math>G-e</math>将<math>u</math>和<math>v</math>染上不同颜色的着色方式有<math>P(G,k)</math>种。
所以图<math>G-e</math>的不同着色方式数目为
:<math>P(G-e,k)=P(G/e,k)+P(G,k)</math>

===加点或减点===
若点<math>v</math>在图<math>G</math>上与其它所有点连边，则所有点的颜色都与该点的颜色互异，记除去顶点<math>v</math>的图为<math>G-v</math>。
:<math>P(G,t)=tP(G-v,t-1)</math>
:<math>P(K_n,t)=tP(K_{n-1},t-1)=t(t-1)(t-2)...(t-(n-1))</math>
在图<math>G</math>的一边<math>e</math>上添加点<math>v</math>所得图记为<math>G+v_e</math>，两端点着同色时有<math>(t-1)P(G\cdot e)</math>种着色法，两端点着不同色是有<math>(t-2)P(G)</math>种着色法。
:<math>P(G+v_e)=(t-2)P(G)+(t-1)P(G\cdot e)</math><ref name="ditui">{{cite journal|author=林翠琴|year=1987|title=图的色多项式的几个递推公式|journal=数学杂志|issue=3|url=http://www.cnki.com.cn/Article/CJFDTotal-SXZZ198703011.htm|access-date=2015-03-07|archive-date=2016-03-04|archive-url=https://web.archive.org/web/20160304100327/http://www.cnki.com.cn/Article/CJFDTotal-SXZZ198703011.htm}}</ref>

===补图===
[[File:L(G).png|thumb|<math>\overline{L(\overline{G})}</math>为<math>G</math>的[[补图]]的[[线图]]的补图。]]
若<math>G</math>为有<math>n</math>个顶点的图，且它的[[独立数]]<3，
:<math>P(G,t)=(t)_n+a_1(t)_{n-1}+a_2(t)_{n-2}+...+a_{[\frac{n}{2}]}(t)_{[\frac{n}{2}]}</math><ref>{{cite journal|author=刘儒英|year=1986|title=关于图的色多项式|journal=青海师范大学学报(自然科学版)|issue=Z1|url=http://www.cnki.com.cn/Article/CJFDTotal-QHSD1986Z1002.htm|access-date=2015-03-07|archive-date=2019-06-16|archive-url=https://web.archive.org/web/20190616000136/http://www.cnki.com.cn/Article/CJFDTOTAL-QHSD1986Z1002.htm}}</ref>
其中<math>(t)_n</math>表示[[阶乘幂]]，<math>a_i</math>为图<math>\overline{L(\overline{G})}</math>中所含的完全子图<math>K_i</math>的个数。

如右图，<math>\overline{L(\overline{G})}</math>中有5个顶点，6条边，2个三角形，所以<math>P(G,t)=(t)_6+5(t)_5+6(t)_4+2(t)_3</math>

==参考资料==
{{reflist}}

[[Category:图染色]]