色多项式

Template:Refimprove 在代数图论中，色多项式是乔治·戴维·伯克霍夫为了尝试证明四色定理而定义的一种多项式。

色多项式$P(G,t)$的值是在图$G$中顶点的不同的$t$-着色数目，是关于$t$的多项式。

例如当图$G$为一点时，$P(G,t)=t$。

例子

特殊图的色多项式

完全图$K_n$	$t(t-1)(t-2)\cdots (t-(n-1))$
树$T_n$	$t(t-1{)}^{n-1}$
环$C_n$	$(t-1{)}^n+(-1{)}^n(t-1)$
佩特森圖	$t(t-1)(t-2)(t^7-12t^6+67t^5-230t^4+529t^3-814t^2+775t-352)$

性质

给定$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)$

递推公式

对于边uv的边收缩（G / {uv}）示意图。

给定图$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)$

补图

$\overline{L(\stackrel{‾}{G})}$为$G$的补图的线图的补图。

若$G$为有$n$个顶点的图，且它的独立数<3，

$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(\stackrel{‾}{G})}$中所含的完全子图$K_i$的个数。

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