色多项式

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

色多项式$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)\left(t^{7}-12t^{6}+67t^{5}-230t^{4}+529t^{3}-814t^{2}+775t-352\right)$

性质

给定$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({\overline {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({\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}$