图的染色多项式 图的染色多项式是代数图论中的一个重要概念，它通过多项式形式描述了图的可着色方案数。以下将从基础定义出发，逐步深入讲解其性质、计算方法和应用。 1. 问题背景：图的着色 图的着色问题要求为图的顶点分配颜色，使得相邻顶点颜色不同。若能用 \( k \) 种颜色完成着色，则称图是 \( k \)-可着色的。染色多项式 \( P(G, k) \) 表示图 \( G \) 的 \( k \)-着色方案数，其中 \( k \) 为自然数。 2. 染色多项式的定义 对于任意图 \( G \)，其染色多项式 \( P(G, k) \) 满足： \( P(G, k) \) 是关于 \( k \) 的多项式函数。 当 \( k < \chi(G) \)（图的色数）时，\( P(G, k) = 0 \)；当 \( k \geq \chi(G) \) 时，\( P(G, k) > 0 \)。 示例 ： 空图（无边）有 \( n \) 个顶点时，每个顶点可独立选择颜色，故 \( P(G, k) = k^n \)。 完全图 \( K_ n \) 需所有顶点颜色不同，故 \( P(K_ n, k) = k(k-1)(k-2)\cdots(k-n+1) \)。 3. 基本性质与递推关系 染色多项式可通过删除-收缩递推计算： 对任意边 \( e \in E(G) \)，有 \[ P(G, k) = P(G-e, k) - P(G/e, k), \] 其中 \( G-e \) 表示删除边 \( e \)，\( G/e \) 表示收缩边 \( e \)（将边两端点合并）。 推导逻辑 ： \( P(G-e, k) \) 包含边 \( e \) 两端点同色或异色的方案数。 \( P(G/e, k) \) 等价于强制边 \( e \) 两端点同色的方案数（收缩后两点视为一个顶点）。 二者相减即得到要求边 \( e \) 两端点异色的方案数，即 \( G \) 的着色方案。 4. 特殊图的染色多项式 树 ：n 个顶点的树满足 \( P(T, k) = k(k-1)^{n-1} \)。 环图 \( C_ n \) ：递推可得 \( P(C_ n, k) = (k-1)^n + (-1)^n(k-1) \)。 完全二部图 \( K_ {m,n} \) ：需分两部分着色，但公式较复杂，通常通过递推或容斥原理计算。 5. 代数性质与根的特性 整数根 ：染色多项式的所有整数根均非负，且根 0, 1, ..., \( \chi(G)-1 \) 必然出现。 实根 ：所有实根均不大于图的最大度，且除 0 和 1 外均为无理数。 系数符号交替 ：多项式系数正负交替，与图的圈结构相关。 6. 应用与推广 色数计算 ：色数 \( \chi(G) \) 是 \( P(G, k) \) 的最小正整根。 物理与化学 ：用于统计力学中的 Potts 模型（推广的着色问题）。 图同构判别 ：不同构的图可能具有相同染色多项式（如某些树），但多项式可辅助区分特殊图类。 7. 计算复杂性 计算任意图的染色多项式是 #P-难问题（即使求特定 \( k \) 的值也困难）。但对平面图、稀疏图等特殊图类，存在高效算法（如利用平面图分解）。 通过以上步骤，染色多项式从着色计数问题发展为连接组合数学、代数和统计物理的桥梁，其递推性质和根分布揭示了图的深层结构特征。