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

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

例如当图为一点时,

例子

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

性质

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

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

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

  • 的系数为0。

递推公式

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

给定图,那么

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

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

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

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

加点或减点

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

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

[3]

补图

Thumb
补图线图的补图。

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

[4]

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

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

参考资料

Wikiwand in your browser!

Seamless Wikipedia browsing. On steroids.

Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.

Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.