在代数图论中,色多项式是乔治·戴维·伯克霍夫为了尝试证明四色定理而定义的一种多项式。
色多项式
的值是在图
中顶点的不同的
-着色数目,是关于
的多项式。
例如当图
为一点时,
。
特殊图的色多项式 完全图![{\displaystyle K_{n}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ea2b988ea630d2c5571afe47efa3d3b251708acb) | |
树![{\displaystyle T_{n}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4d9241493be76739f2400f258f32c24f9689161f) | |
环![{\displaystyle C_{n}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0301812adb392070d834ca2df4ed97f1cf132f33) | |
佩特森圖 | |
给定
阶图
,色多项式
是关于
的多项式,且满足以下性质[1]:
- 多项式
的次数为
。
的系数为1。
的系数为
。
的系数不为0且正负交替出现。
特别的,设
有
个连通分量,分别为
,那么
的系数为0。 ![{\displaystyle P(G)=\prod _{k=1}^{n}P(G_{k})}](https://wikimedia.org/api/rest_v1/media/math/render/svg/c708e203830f64a862dd3d55ff72536e5a995691)
对于边uv的边收缩(G / {uv})示意图。 给定图
与
,那么
![{\displaystyle P(G,k)=P(G-e,k)-P(G/e,k)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/df02ac9de6a60942dcc30a7b3cf4a6816d3b82ac)
其中
代表边收缩:令
所连接的两个顶点计为
和
,而边收缩会使顶点
和
合并成一个新的顶点
,并使原本与
和
相连的所有边都连到
。
证明[2] 假设
所连接的两个顶点为
和
,考虑图
。
- 当
和
的颜色相同时,这种着色方式也是
的一种合理着色方式,反之亦然。所以对图
将
和
染上相同颜色的着色方式有
种。 - 当
和
的颜色不同时,这种着色方式也是
的一种合理着色方式,反之亦然。所以对图
将
和
染上不同颜色的着色方式有
种。
所以图
的不同着色方式数目为
![{\displaystyle P(G-e,k)=P(G/e,k)+P(G,k)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/446d11e1cc3129f72c4887583e8a4b23d888b507)
若点
在图
上与其它所有点连边,则所有点的颜色都与该点的颜色互异,记除去顶点
的图为
。
![{\displaystyle P(G,t)=tP(G-v,t-1)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/13d560d9a2f379b32351ead0b1c2753a6f2539d8)
![{\displaystyle P(K_{n},t)=tP(K_{n-1},t-1)=t(t-1)(t-2)...(t-(n-1))}](https://wikimedia.org/api/rest_v1/media/math/render/svg/8348226e22441f6fe8111008fa92426e6b647a7f)
在图
的一边
上添加点
所得图记为
,两端点着同色时有
种着色法,两端点着不同色是有
种着色法。
[3]
![](//upload.wikimedia.org/wikipedia/commons/thumb/f/fc/L%28G%29.png/220px-L%28G%29.png)
为
的补图的线图的补图。 若
为有
个顶点的图,且它的独立数<3,
[4]
其中
表示阶乘幂,
为图
中所含的完全子图
的个数。
如右图,
中有5个顶点,6条边,2个三角形,所以
- ^ Whitney, Hassler, The coloring of graphs, Annals of Mathematics (JSTOR), 1932: 688–718
- ^ 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
- ^ 林翠琴. 图的色多项式的几个递推公式. 数学杂志. 1987, (3) [2015-03-07]. (原始内容存档于2016-03-04).
- ^ 刘儒英. 关于图的色多项式. 青海师范大学学报(自然科学版). 1986, (Z1) [2015-03-07]. (原始内容存档于2019-06-16).