图的染色多项式

图的染色多项式是图论中一个重要的计数工具，它通过一个多项式来精确描述一个图可以用多少种不同的方式着色。

1. 基本思想与定义

   • 首先，回忆图的着色概念：给一个图的每个顶点分配一种颜色，使得任何一条边连接的两个顶点颜色不同。这被称为图的正常顶点着色。
   • 如果我们有 λ 种不同的颜色，一个自然的问题是：对于一个给定的图 G，有多少种不同的正常着色方法？我们把这个数量记作 P(G, λ)。
   • 一个关键的发现是，对于任意一个图 G，这个着色方案的数量 P(G, λ) 总是可以表示为一个关于 λ 的多项式。这个多项式就被称为图 G 的染色多项式。
   • 例如，一个由三个顶点构成的完全图 K₃（即三角形），如果你有 λ 种颜色，给第一个顶点有 λ 种选择，第二个顶点有 (λ-1) 种选择（不能和第一个顶点同色），第三个顶点有 (λ-2) 种选择（不能和前两个顶点同色）。所以 P(K₃, λ) = λ(λ-1)(λ-2)。这确实是一个关于 λ 的多项式。

2. 基本性质与计算

   • 简单图的染色多项式：对于最简单的图——n 个顶点、没有边的空图 Īₙ，每个顶点都可以任意选择 λ 种颜色中的一种，且不会有边冲突。因此，P(Īₙ, λ) = λⁿ。
   • 树的染色多项式：一棵有 n 个顶点的树。你可以从根节点开始着色，它有 λ 种选择。它的每个子节点都有 (λ-1) 种选择（不能和父节点同色），以此类推。最终，P(树, λ) = λ(λ-1)ⁿ⁻¹。
   • 递推关系（减边-缩边递推）：这是计算染色多项式最核心的工具。对于图 G 中的任意一条边 e（e 不是自环），其染色多项式满足以下关系：
     P(G, λ) = P(G\e, λ) - P(G/e, λ)
     • G\e 表示从图 G 中删除边 e 后得到的图。
     • G/e 表示将图 G 中的边 e “收缩”：即把边 e 的两个端点合并成一个新的顶点，并与原来与这两个端点相连的所有其他边连接。
   • 这个递推关系的逻辑是：图 G 的所有用 λ 种颜色对 G\e 的着色方案可以分为两类：一类是边 e 的两个端点颜色不同的（这正好是 G 的正常着色），另一类是边 e 的两个端点颜色相同的（这种着色方案对应于对收缩后的图 G/e 的正常着色）。因此，P(G\e, λ) = P(G, λ) + P(G/e, λ)，移项即得上述公式。通过反复应用此递推，最终可以将任意图的染色多项式化为一些已知多项式（如空图、完全图）的组合。

3. 进一步的性质与结论

   • 多项式形式：一个图的染色多项式必定是首一多项式（最高次项系数为1），次数等于图的顶点数。它的系数是整数，并且系数的符号是正负交替的。
   • 与图的连通性的关系：如果一个图是由 k 个连通分支 G₁, G₂, ..., Gk 组成的非连通图，那么整个图的染色多项式是各个连通分支染色多项式的乘积：P(G, λ) = P(G₁, λ) * P(G₂, λ) * ... * P(Gk, λ)。这是因为对各分支的着色是相互独立的。
   • 色数：图的色数 χ(G) 是指对图进行正常着色所需的最少颜色数。染色多项式与色数有直接联系：图 G 的色数 χ(G) 是使得 P(G, k) > 0 的最小正整数 k。也就是说，色数是染色多项式的第一个正整数根之后的那个整数。

4. 意义与应用

   • 染色多项式将图的着色这个组合计数问题代数化了，使我们能运用多项式理论的工具来研究着色问题。
   • 它可以用来区分不同构的图。如果两个图的染色多项式不同，那么它们一定不是同构的。（但反之不一定成立，存在染色多项式相同但不同构的图，称为“同谱图”或“染色等价图”）。
   • 它在统计物理中有重要应用，例如在计算波特模型的配分函数时，问题可以转化为计算特定图的染色多项式。