在代数图论中，色多项式是乔治·戴维·伯克霍夫为了尝试证明四色定理而定义的一种多项式。
色多项式P(G,t)的值是在图G中顶点的不同的t-着色数目，是关于t的多项式。
例如当图G为一点时，P(G,t)=t。
例子
性质
给定n阶图G，色多项式P(G, t)是关于t的多项式，且满足以下性质：
- 多项式P(G, t)的次数为n。
- t^n的系数为1。
- t^{n-1}的系数为-|E(G)|。
- t^c,\dots,t^n的系数不为0且正负交替出现。
特别的，设G有c个连通分量，分别为G_1,\dots,G_c，那么
- t^0,\dots,t^{c-1}的系数为0。
- P(G)=\prod_{k=1}^n P(G_k)
递推公式
给定图G与e\in E(G)，那么
:P(G,k)=P(G-e,k)-P(G/e,k)
其中G/e代表边收缩：令e所连接的两个顶点计为u和v，而边收缩会使顶点u和v合并成一个新的顶点w，并使原本与u和v相连的所有边都连到w。
证明 假设e所连接的两个顶点为u和v，考虑图G-e。
- 当u和v的颜色相同时，这种着色方式也是G/e的一种合理着色方式，反之亦然。所以对图G-e将u和v染上相同颜色的着色方式有P(G/e,k)种。
- 当u和v的颜色不同时，这种着色方式也是G的一种合理着色方式，反之亦然。所以对图G-e将u和v染上不同颜色的着色方式有P(G,k)种。
所以图G-e的不同着色方式数目为
:P(G-e,k)=P(G/e,k)+P(G,k)
加点或减点
若点v在图G上与其它所有点连边，则所有点的颜色都与该点的颜色互异，记除去顶点v的图为G-v。
:P(G,t)=tP(G-v,t-1)
:P(K_n,t)=tP(K_{n-1},t-1)=t(t-1)(t-2)...(t-(n-1))
在图G的一边e上添加点v所得图记为G+v_e，两端点着同色时有(t-1)P(G\cdot e)种着色法，两端点着不同色是有(t-2)P(G)种着色法。
:P(G+v_e)=(t-2)P(G)+(t-1)P(G\cdot e)
补图
的线图的补图。]]
若G为有n个顶点的图，且它的独立数P(G,t)=(t)_n+a_1(t)_{n-1}+a_2(t)_{n-2}+...+a_{[\frac{n}{2}]}(t)_{[\frac{n}{2}]}
其中(t)_n表示阶乘幂，a_i为图\overline{L(\overline{G})}中所含的完全子图K_i的个数。
如右图，\overline{L(\overline{G})}中有5个顶点，6条边，2个三角形，所以P(G,t)=(t)_6+5(t)_5+6(t)_4+2(t)_3
参考资料
评论 (0)