色多项式

在代数图论中，色多项式是乔治·戴维·伯克霍夫为了尝试证明四色定理而定义的一种多项式。

色多项式${\displaystyle P(G,t)}$的值是在图${\displaystyle G}$中顶点的不同着色方法数目，是关于不同颜色数目${\displaystyle t}$的函数。

例如当图${\displaystyle G}$为一点时，${\displaystyle P(G,t)=t}$。

若图${\displaystyle G}$是不连通图，可分成${\displaystyle n}$个连通片${\displaystyle G_1,G_2,\cdots <!--\; \cdots \; -->,G_n}$，图${\displaystyle G}$的着色方法数等于所有连通片的着色方法数的乘积。

当两个顶点没有连边时，意味着两个顶点的颜色可以互异（连边），也可以相等（点重合）。

若点${\displaystyle v}$在图${\displaystyle G}$上与其它所有点连边，则所有点的颜色都与该点的颜色互异，记除去顶点${\displaystyle v}$的图为${\displaystyle G-<!--\; -\; -->v}$。

在图${\displaystyle G}$的一边${\displaystyle e}$上添加点${\displaystyle v}$所得图记为${\displaystyle G+v_e}$，两端点着同色时有${\displaystyle (t-<!--\; -\; -->1)P(G\cdot <!--\; \cdot \; -->e)}$种着色法，两端点着不同色是有${\displaystyle (t-<!--\; -\; -->2)P(G)}$种着色法。

若${\displaystyle G}$为有${\displaystyle n}$个顶点的图，且它的独立数<3，

其中${\displaystyle (t{)}_n}$表示阶乘幂，${\displaystyle a_i}$为图${\displaystyle \stackrel{¯<!--\; ¯\; -->}{L(\stackrel{¯<!--\; ¯\; -->}{G})}}$中所含的完全子图${\displaystyle K_i}$的个数。

如右图，${\displaystyle \stackrel{¯<!--\; ¯\; -->}{L(\stackrel{¯<!--\; ¯\; -->}{G})}}$中有5个顶点，6条边，2个三角形，所以${\displaystyle P(G,t)=(t{)}_6+5(t{)}_5+6(t{)}_4+2(t{)}_3}$