色多项式 - 维基百科，自由的百科全书

此條目需要补充更多来源。 (2015年3月7日) 请协助補充多方面可靠来源以改善这篇条目，无法查证的内容可能會因為异议提出而被移除。 致使用者：请搜索一下条目的标题（来源搜索："色多项式" — 网页、新闻、书籍、学术、图像），以检查网络上是否存在该主题的更多可靠来源（判定指引）。

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

色多项式${\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})}$

递推公式[编辑]

给定图${\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 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}}$

参考资料[编辑]