色多项式

色多项式记录一张有限图在给定颜色数下有多少种合法顶点着色。颜色被视为有区别的标签：如果两种着色交换了红、蓝，它们通常计为两种，而不是自动视为同一种。

定义和简单计数

对有限图 $G$ 和非负整数 $q$，记 $P_G(q)$ 为从 $q$ 个指定颜色中给每个顶点选一种、且相邻顶点颜色不同的方法数。这个计数能由一个关于 $q$ 的多项式表示，称为图的色多项式。

没有边的 $n$ 顶点图，所有顶点独立选择颜色，所以 $P(q)=q^n$。三角形的第一个顶点有 $q$ 种颜色，第二个必须与它不同，有 $q-1$ 种；第三个与前两个均相邻，有 $q-2$ 种。因此 $$P_{K_3}(q)=q(q-1)(q-2).$$ 例如指定红、蓝、绿三色时，三角形恰有 $3\times 2\times 1=6$ 种着色。

删边—缩边递推

取简单图中一条边 $e=uv$。记 $G-e$ 为只删除该边的图；记 $G/e$ 为将 $u,v$ 合并成一个顶点的图。缩边时去掉由 $e$ 形成的环，重复的平行边可以合并，因为它们施加的是同一条不同色约束。

在 $G-e$ 的合法着色中，若 $u,v$ 颜色不同，它同时是 $G$ 的合法着色；若颜色相同，合并这两个顶点便得到 $G/e$ 的合法着色。两类互不重叠且覆盖全部情况，故 $$P_G(q)=P_{G-e}(q)-P_{G/e}(q).$$ 删边减少一条边，缩边减少一个顶点。以无边图为起点递归，即可证明计数函数是多项式。

计算四环

对四环 $C_4$ 删除一条边，得到四顶点路径；缩去该边，得到三角形。路径的第一个顶点有 $q$ 种颜色，每个后继顶点各有 $q-1$ 种，所以 $$\begin{array}{cc}{P}_{C_4}(q)& =q(q-1{)}^3-q(q-1)(q-2)\\ & =q(q-1)(q^2-3q+3).\end{array}$$ 代入 $q=2$ 得 2：先定一个顶点颜色后，其余顶点只能交替着色。代入 $q=3$ 得 $3\cdot 2\cdot 3=18$。

对红色标记的边，分别执行删边和缩边。

适用边界

色多项式的计数含义直接适用于非负整数 $q$；代入其他数得到的是多项式的代数取值，不自动表示某个着色数量。最小使 $P_G(q)>0$ 的正整数是图的顶点色数。图中的环若连接顶点自身，会使合法着色不存在；此时色多项式恒为零。