图的着色多项式 图的着色多项式是图论中一个重要的计数多项式，它描述了用 \( k \) 种颜色对图的顶点进行正常着色（相邻顶点颜色不同）的方案数。以下逐步介绍其核心概念与性质： 1. 基本定义 设 \( G \) 是一个无向图，\( k \) 表示颜色数量。 着色多项式 \( P(G, k) \) 是一个关于 \( k \) 的多项式，其值等于用 \( k \) 种颜色对 \( G \) 的顶点进行正常着色的不同方案数。 示例 ： 若 \( G \) 是 \( n \) 个顶点的空图（无边），则 \( P(G, k) = k^n \)（每个顶点可任意选择颜色）。 若 \( G \) 是完全图 \( K_ n \)，则 \( P(G, k) = k(k-1)(k-2)\cdots(k-n+1) \)。 2. 递推关系：删除-收缩公式 着色多项式可通过递归方式计算，核心工具是 删除-收缩公式 ： 对任意边 \( e = uv \)，有： \[ P(G, k) = P(G-e, k) - P(G/e, k) \] 其中： \( G-e \) 表示删除边 \( e \) 后的图； \( G/e \) 表示收缩边 \( e \)（将顶点 \( u, v \) 合并为一个顶点）。 推导逻辑 ： \( P(G-e, k) \) 包含两种着色方案：\( u, v \) 颜色相同或不同。 \( P(G/e, k) \) 对应 \( u, v \) 颜色相同的方案数。 两者相减即得 \( u, v \) 颜色不同的方案数，即 \( P(G, k) \)。 3. 着色多项式的性质 次数与系数 ： \( P(G, k) \) 是次数为 \( n \)（顶点数）的多项式，首项为 \( k^n \)。 系数交替符号，且常数项为 0（因为至少需要一种颜色）。 连通图的性质 ： 若 \( G \) 连通，则 \( P(G, k) \) 的系数中 \( k^{n-1} \) 的系数为 \( -m \)（\( m \) 为边数）。 图不变量 ： 同构的图具有相同的着色多项式，但逆命题不成立（存在不同构的图具有相同着色多项式）。 4. 特殊图的着色多项式 树 ： 若 \( G \) 是 \( n \) 个顶点的树，则 \( P(G, k) = k(k-1)^{n-1} \)。 环图 \( C_ n \) ： \[ P(C_ n, k) = (k-1)^n + (-1)^n(k-1) \] 平面图 ： 四色定理等价于“对任意平面图 \( G \)，有 \( P(G, 4) > 0 \)”。 5. 与图结构的关系 色数与根 ： 图 \( G \) 的色数 \( \chi(G) \) 是满足 \( P(G, k) > 0 \) 的最小正整数 \( k \)。 零根性质 ： 所有整数根 \( k \) 必须满足 \( k \leq \Delta(G) \)（最大度），但非整数根可能更复杂。 著名的 Birkhoff–Lewis定理 指出平面图的着色多项式无实根于 \( (-\infty, 4) \)。 6. 应用与扩展 物理与统计 ： 着色多项式与Potts模型（统计物理）的配分函数密切相关。 算法复杂性 ： 计算任意图的着色多项式是 #P-难问题，但对特定图类（如弦图）存在高效算法。 推广 ： 可扩展为 色对称函数 ，进一步关联到对称群表示论。 通过以上步骤，着色多项式从基本计数工具逐步展现出与图结构、代数组合及物理模型的丰富联系。