[科普中國]-色多項式

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

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

色多項式的值是在圖中頂點的不同著色方法數(shù)目，是關(guān)于不同顏色數(shù)目 的函數(shù)。

例如當圖 為一點時， 。1

特殊圖的色多項式

|| ||

性質(zhì)不連通圖若圖 是不連通圖，可分成 個連通片 ，圖 的著色方法數(shù)等于所有連通片的著色方法數(shù)的乘積。

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

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

環(huán)圖有遞推公式：

為三角形圖，

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

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

補圖若 為有 個頂點的圖，且它的獨立數(shù)