色多项式

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

色多项式${\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）.