色多项式

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

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

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

例子

特殊图的色多项式

完全图${\displaystyle K_{n}}$	${\displaystyle t(t-1)(t-2)\cdots (t-(n-1))}$
树${\displaystyle T_{n}}$	${\displaystyle t(t-1)^{n-1}}$
环${\displaystyle C_{n}}$	${\displaystyle (t-1)^{n}+(-1)^{n}(t-1)}$
佩特森圖	${\displaystyle t(t-1)(t-2)\left(t^{7}-12t^{6}+67t^{5}-230t^{4}+529t^{3}-814t^{2}+775t-352\right)}$

性质

给定${\displaystyle n}$ 阶图${\displaystyle G}$ ，色多项式${\displaystyle P(G,t)}$ 是关于${\displaystyle t}$ 的多项式，且满足以下性质^[1]：

• 多项式${\displaystyle P(G,t)}$ 的次数为${\displaystyle n}$ 。
• ${\displaystyle t^{n}}$ 的系数为1。
• ${\displaystyle t^{n-1}}$ 的系数为${\displaystyle -|E(G)|}$ 。
• ${\displaystyle t^{c},\dots ,t^{n}}$ 的系数不为0且正负交替出现。

特别的，设${\displaystyle G}$ 有${\displaystyle c}$ 个连通分量，分别为${\displaystyle G_{1},\dots ,G_{c}}$ ，那么

• ${\displaystyle t^{0},\dots ,t^{c-1}}$ 的系数为0。
• ${\displaystyle P(G)=\prod _{k=1}^{n}P(G_{k})}$ 

递推公式

 

对于边uv的边收缩（G / {uv}）示意图。

给定图${\displaystyle G}$ 与${\displaystyle e\in E(G)}$ ，那么

${\displaystyle P(G,k)=P(G-e,k)-P(G/e,k)}$ 

其中${\displaystyle G/e}$ 代表边收缩：令${\displaystyle e}$ 所连接的两个顶点计为${\displaystyle u}$ 和${\displaystyle v}$ ，而边收缩会使顶点${\displaystyle u}$ 和${\displaystyle v}$ 合并成一个新的顶点${\displaystyle w}$ ，并使原本与${\displaystyle u}$ 和${\displaystyle v}$ 相连的所有边都连到${\displaystyle w}$ 。

证明^[2] 假设${\displaystyle e}$ 所连接的两个顶点为${\displaystyle u}$ 和${\displaystyle v}$ ，考虑图${\displaystyle G-e}$ 。

• 当${\displaystyle u}$ 和${\displaystyle v}$ 的颜色相同时，这种着色方式也是${\displaystyle G/e}$ 的一种合理着色方式，反之亦然。所以对图${\displaystyle G-e}$ 将${\displaystyle u}$ 和${\displaystyle v}$ 染上相同颜色的着色方式有${\displaystyle P(G/e,k)}$ 种。
• 当${\displaystyle u}$ 和${\displaystyle v}$ 的颜色不同时，这种着色方式也是${\displaystyle G}$ 的一种合理着色方式，反之亦然。所以对图${\displaystyle G-e}$ 将${\displaystyle u}$ 和${\displaystyle v}$ 染上不同颜色的着色方式有${\displaystyle P(G,k)}$ 种。

所以图${\displaystyle G-e}$ 的不同着色方式数目为

${\displaystyle P(G-e,k)=P(G/e,k)+P(G,k)}$ 

加点或减点

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

${\displaystyle P(G,t)=tP(G-v,t-1)}$ 

${\displaystyle P(K_{n},t)=tP(K_{n-1},t-1)=t(t-1)(t-2)...(t-(n-1))}$ 

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

${\displaystyle P(G+v_{e})=(t-2)P(G)+(t-1)P(G\cdot e)}$ ^[3]

补图

 

${\displaystyle {\overline {L({\overline {G}})}}}$ 为${\displaystyle G}$ 的补图的线图的补图。

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

${\displaystyle P(G,t)=(t)_{n}+a_{1}(t)_{n-1}+a_{2}(t)_{n-2}+...+a_{[{\frac {n}{2}}]}(t)_{[{\frac {n}{2}}]}}$ ^[4]

其中${\displaystyle (t)_{n}}$ 表示阶乘幂，${\displaystyle a_{i}}$ 为图${\displaystyle {\overline {L({\overline {G}})}}}$ 中所含的完全子图${\displaystyle K_{i}}$ 的个数。

如右图，${\displaystyle {\overline {L({\overline {G}})}}}$ 中有5个顶点，6条边，2个三角形，所以${\displaystyle P(G,t)=(t)_{6}+5(t)_{5}+6(t)_{4}+2(t)_{3}}$ 

参考资料

1. Whitney, Hassler, The coloring of graphs, Annals of Mathematics (JSTOR), 1932: 688–718 
2. Harris, John; Hirst, Jeffry L.; Mossinghoff, Michael, Combinatorics and Graph Theory, Undergraduate Texts in Mathematics, Springer-Verlag New York: 98–99, 2008, ISBN 978-0-387-79711-3, doi:10.1007/978-0-387-79711-3 
3. 林翠琴. . 数学杂志. 1987, (3) [2015-03-07]. （原始内容存档于2016-03-04）. 
4. 刘儒英. . 青海师范大学学报(自然科学版). 1986, (Z1) [2015-03-07]. （原始内容存档于2019-06-16）.