色多項式

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

色多項式${\displaystyle P(G,t)}$的值是在圖${\displaystyle G}$中頂點的不同的${\displaystyle t}$-著色數目，是關於${\displaystyle t}$的多項式。

例如當圖${\displaystyle G}$為一點時，${\displaystyle P(G,t)=t}$。

例子

特殊圖的色多項式

完全圖${\displaystyle K_{n}}$	${\displaystyle t(t-1)(t-2)\cdots (t-(n-1))}$
樹${\displaystyle T_{n}}$	${\displaystyle t(t-1)^{n-1}}$
環${\displaystyle C_{n}}$	${\displaystyle (t-1)^{n}+(-1)^{n}(t-1)}$
佩特森圖	${\displaystyle t(t-1)(t-2)\left(t^{7}-12t^{6}+67t^{5}-230t^{4}+529t^{3}-814t^{2}+775t-352\right)}$

性質

給定${\displaystyle n}$階圖${\displaystyle G}$，色多項式${\displaystyle P(G,t)}$是關於${\displaystyle t}$的多項式，且滿足以下性質^[1]：

• 多項式${\displaystyle P(G,t)}$的次數為${\displaystyle n}$。
• ${\displaystyle t^{n}}$的係數為1。
• ${\displaystyle t^{n-1}}$的係數為${\displaystyle -|E(G)|}$。
• ${\displaystyle t^{c},\dots ,t^{n}}$的係數不為0且正負交替出現。

特別的，設${\displaystyle G}$有${\displaystyle c}$個連通分量，分別為${\displaystyle G_{1},\dots ,G_{c}}$，那麼

• ${\displaystyle t^{0},\dots ,t^{c-1}}$的係數為0。
• ${\displaystyle P(G)=\prod _{k=1}^{n}P(G_{k})}$

遞推公式

對於邊uv的邊收縮（G / {uv}）示意圖。

給定圖${\displaystyle G}$與${\displaystyle e\in E(G)}$，那麼

${\displaystyle P(G,k)=P(G-e,k)-P(G/e,k)}$

其中${\displaystyle G/e}$代表邊收縮：令${\displaystyle e}$所連接的兩個頂點計為${\displaystyle u}$和${\displaystyle v}$，而邊收縮會使頂點${\displaystyle u}$和${\displaystyle v}$合併成一個新的頂點${\displaystyle w}$，並使原本與${\displaystyle u}$和${\displaystyle v}$相連的所有邊都連到${\displaystyle w}$。

證明^[2] 假設${\displaystyle e}$所連接的兩個頂點為${\displaystyle u}$和${\displaystyle v}$，考慮圖${\displaystyle G-e}$。

• 當${\displaystyle u}$和${\displaystyle v}$的顏色相同時，這種著色方式也是${\displaystyle G/e}$的一種合理著色方式，反之亦然。所以對圖${\displaystyle G-e}$將${\displaystyle u}$和${\displaystyle v}$染上相同顏色的著色方式有${\displaystyle P(G/e,k)}$種。
• 當${\displaystyle u}$和${\displaystyle v}$的顏色不同時，這種著色方式也是${\displaystyle G}$的一種合理著色方式，反之亦然。所以對圖${\displaystyle G-e}$將${\displaystyle u}$和${\displaystyle v}$染上不同顏色的著色方式有${\displaystyle P(G,k)}$種。

所以圖${\displaystyle G-e}$的不同著色方式數目為

${\displaystyle P(G-e,k)=P(G/e,k)+P(G,k)}$

加點或減點

若點${\displaystyle v}$在圖${\displaystyle G}$上與其它所有點連邊，則所有點的顏色都與該點的顏色互異，記除去頂點${\displaystyle v}$的圖為${\displaystyle G-v}$。

${\displaystyle P(G,t)=tP(G-v,t-1)}$

${\displaystyle P(K_{n},t)=tP(K_{n-1},t-1)=t(t-1)(t-2)...(t-(n-1))}$

在圖${\displaystyle G}$的一邊${\displaystyle e}$上添加點${\displaystyle v}$所得圖記為${\displaystyle G+v_{e}}$，兩端點著同色時有${\displaystyle (t-1)P(G\cdot e)}$種著色法，兩端點著不同色是有${\displaystyle (t-2)P(G)}$種著色法。

${\displaystyle P(G+v_{e})=(t-2)P(G)+(t-1)P(G\cdot e)}$^[3]

補圖

${\displaystyle {\overline {L({\overline {G}})}}}$為${\displaystyle G}$的補圖的線圖的補圖。

若${\displaystyle G}$為有${\displaystyle n}$個頂點的圖，且它的獨立數<3，

${\displaystyle P(G,t)=(t)_{n}+a_{1}(t)_{n-1}+a_{2}(t)_{n-2}+...+a_{[{\frac {n}{2}}]}(t)_{[{\frac {n}{2}}]}}$^[4]

其中${\displaystyle (t)_{n}}$表示階乘冪，${\displaystyle a_{i}}$為圖${\displaystyle {\overline {L({\overline {G}})}}}$中所含的完全子圖${\displaystyle K_{i}}$的個數。

如右圖，${\displaystyle {\overline {L({\overline {G}})}}}$中有5個頂點，6條邊，2個三角形，所以${\displaystyle P(G,t)=(t)_{6}+5(t)_{5}+6(t)_{4}+2(t)_{3}}$