色多項式

在代數圖論中，色多項式是喬治·戴維·伯克霍夫為了嘗試證明四色定理而定義的一種多項式。

色多項式$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}$