色多项式

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

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

例如当图为一点时,

例子

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

性质

给定 阶图 ,色多项式 是关于 的多项式,且满足以下性质[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).