图的染色多项式最早是由 George. D. Birkhoff 为了解决四色问题而提出的, 当然我们现在知道他并没有完全成功, 就如同 Kummer 的理想理论之于费马大定理.
$\gdef\spaces#1{~ #1 ~}$
$\gdef\quads#1{\quad #1 \quad}$
$\gdef\without{\setminus}$
对于简单图 $G$, 其色多项式 $\pi(G)$ 成立如下关系
$$ \pi(G) \spaces= \pi(G \without e) \spaces- \pi(G / e), \quad \forall ~ e \in \text{Edge}(G) $$
$\gdef\sstr#1{~#1~}$
假定边 $e$ 的两个端点分别为 $A,B$, 不难发现
$$
\begin{aligned}
\pi(G \without e)
&\spaces= \pi(G \without e \sstr{中} A,B ~同色的部分) ~ + ~ \pi(G \without e \sstr{中} A,B ~异色的部分) \\
&\spaces= \pi(G / e) ~ + ~ \pi(G)
\end{aligned}
$$
此处, $G \without e$ 是将 $G$ 的边 $e$ 删去, $G/e$ 是将 $e$ 两侧的顶点合并为一个.
这个结果可等价地叙述成连接的版本, 可称为 “连接–收缩公式”. 对于简单图 $G = (V, E)$
$$ \pi(G) \spaces= \pi(G + uv) \spaces+ \pi(G / uv), \quad \forall ~ uv \notin E $$
这里, $G+e$ 是指将 $e$ 两侧的顶点连接, $u v$ 是指顶点 $u, v$ 连接得到的边.
利用此结果, 可以轻易计算较为复杂的简单图的染色数, 如
.
现在, 由于 删除–收缩公式, 可以知道 $\pi(C_4)$ 的着色数是 $4$ 点径图与三点环图 $C_3$ 着色数的差, 即
