色多項式

在代數圖論中，色多項式是喬治·戴維·伯克霍夫為了嘗試證明四色定理而定義的一種多項式。

基本介紹

• 中文名：色多項式
• 外文名：Chromatic polynomial
• 領域：數學
• 適用領域：代數圖論

定義

在代數圖論中，色多項式是喬治·戴維·伯克霍夫為了嘗試證明四色定理而定義的一種多項式。

色多項式的值是在圖中頂點的不同著色方法數目，是關於不同顏色數目 的函式。

例如當圖 為一點時， 。

特殊圖的色多項式

完全圖
有n個頂點的樹
環圖
佩特森圖

性質

不連通圖

若圖 是不連通圖，可分成 個連通片 ，圖 的著色方法數等於所有連通片的著色方法數的乘積。

加邊或減邊

當兩個頂點沒有連邊時，意味著兩個頂點的顏色可以互異（連邊），也可以相等（點重合）。

樹圖上每消一根樹枝 都乘以 ，消掉 根樹枝後剩下一點。

環圖有遞推公式：

為三角形圖，

加點或減點

若點 在圖 上與其它所有點連邊，則所有點的顏色都與該點的顏色互異，記除去頂點 的圖為 。

在圖 的一邊 上添加點 所得圖記為 ，兩端點著同色時有 種著色法，兩端點著不同色是有 種著色法。

補圖

若 為有 個頂點的圖，且它的獨立數<3，

其中表示階乘冪，為圖中所含的完全子圖的個數。

如右圖，中有5個頂點，6條邊，2個三角形，所以