在代数图论中,色多项式是乔治·戴维·伯克霍夫为了尝试证明四色定理而定义的一种多项式。
色多项式的值是在图中顶点的不同的-着色数目,是关于的多项式。
例如当图为一点时,。
特殊图的色多项式
完全图 |
|
树 |
|
环 |
|
佩特森圖 |
|
给定阶图,色多项式是关于的多项式,且满足以下性质[1]:
- 多项式的次数为。
- 的系数为1。
- 的系数为。
- 的系数不为0且正负交替出现。
特别的,设有个连通分量,分别为,那么
- 的系数为0。
给定图与,那么
其中代表边收缩:令所连接的两个顶点计为和,而边收缩会使顶点和合并成一个新的顶点,并使原本与和相连的所有边都连到。
证明[2] 假设所连接的两个顶点为和,考虑图。
- 当和的颜色相同时,这种着色方式也是的一种合理着色方式,反之亦然。所以对图将和染上相同颜色的着色方式有种。
- 当和的颜色不同时,这种着色方式也是的一种合理着色方式,反之亦然。所以对图将和染上不同颜色的着色方式有种。
所以图的不同着色方式数目为
若点在图上与其它所有点连边,则所有点的颜色都与该点的颜色互异,记除去顶点的图为。
在图的一边上添加点所得图记为,两端点着同色时有种着色法,两端点着不同色是有种着色法。
- [3]
若为有个顶点的图,且它的独立数<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).