色多项式

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

色多项式的值是在图中顶点的不同的-着色数目，是关于的多项式。

例如当图为一点时，。

例子
+特殊图的色多项式 完全图   树      环   佩特森圖  

性质
给定阶图，色多项式是关于的多项式，且满足以下性质：
 多项式的次数为。
 的系数为1。
 的系数为。
 的系数不为0且正负交替出现。
特别的，设有个连通分量，分别为，那么
 的系数为0。

递推公式
给定图与，那么

其中代表边收缩：令所连接的两个顶点计为和，而边收缩会使顶点和合并成一个新的顶点，并使原本与和相连的所有边都连到。

证明 假设所连接的两个顶点为和，考虑图。
 当和的颜色相同时，这种着色方式也是的一种合理着色方式，反之亦然。所以对图将和染上相同颜色的着色方式有种。
 当和的颜色不同时，这种着色方式也是的一种合理着色方式，反之亦然。所以对图将和染上不同颜色的着色方式有种。
所以图的不同着色方式数目为

加点或减点
若点在图上与其它所有点连边，则所有点的颜色都与该点的颜色互异，记除去顶点的图为。

在图的一边上添加点所得图记为，两端点着同色时有种着色法，两端点着不同色是有种着色法。

补图
若为有个顶点的图，且它的独立数<3，

其中表示阶乘幂，为图中所含的完全子图的个数。

如右图，中有5个顶点，6条边，2个三角形，所以

参考资料

Category:图染色