跳转到内容

色多项式

维基百科,自由的百科全书

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

色多项式的值是在顶点的不同的-着色数目,是关于的多项式。

例如当图为一点时,

例子

特殊图的色多项式
完全图
佩特森图

性质

给定阶图,色多项式是关于的多项式,且满足以下性质[1]

  • 多项式的次数为
  • 的系数为1。
  • 的系数为
  • 的系数不为0且正负交替出现。

特别的,设个连通分量,分别为,那么

  • 的系数为0。

递推公式

对于边uv的边收缩(G / {uv})示意图。

给定图,那么

其中代表边收缩:令所连接的两个顶点计为,而边收缩会使顶点合并成一个新的顶点,并使原本与相连的所有边都连到

证明[2] 假设所连接的两个顶点为,考虑图

  • 的颜色相同时,这种着色方式也是的一种合理着色方式,反之亦然。所以对图染上相同颜色的着色方式有种。
  • 的颜色不同时,这种着色方式也是的一种合理着色方式,反之亦然。所以对图染上不同颜色的着色方式有种。

所以图的不同着色方式数目为

加点或减点

若点在图上与其它所有点连边,则所有点的颜色都与该点的颜色互异,记除去顶点的图为

在图的一边上添加点所得图记为,两端点着同色时有种着色法,两端点着不同色是有种着色法。

[3]

补图

补图线图的补图。

为有个顶点的图,且它的独立数<3,

[4]

其中表示阶乘幂为图中所含的完全子图的个数。

如右图,中有5个顶点,6条边,2个三角形,所以

参考资料

  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).