Definition. 染色图 [chromatic-graph]

  • July 21, 2024
  • kokic

图的染色多项式最早是由 George. D. Birkhoff 为了解决四色问题而提出的, 当然我们现在知道他并没有完全成功, 就如同 Kummer 的理想理论之于费马大定理.

Theorem. 删除–收缩公式 [deletion-contraction]

  • July 21, 2024
  • kokic

$\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) $$

Proof. [deletion-contraction-proof]

  • July 21, 2024
  • kokic

$\gdef\quads#1{\quad #1 \quad}$ $\gdef\spaces#1{~ #1 ~}$ $\gdef\without{\setminus}$

$\gdef\str#1{{\footnotesize #1}}$ $\gdef\sstr#1{~{\footnotesize #1}~}$

假定边 $e$ 的两个端点分别为 $A,B$, 不难发现 $$\begin{aligned} \pi(G \without e) &\spaces= \pi(G \without e \sstr{中} A,B ~\str{同色的部分}) ~ + ~ \pi(G \without e \sstr{中} A,B ~\str{异色的部分}) \\ &\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$ 着色数的差, 即