跳至內容

色多項式

維基百科,自由的百科全書

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

色多項式的值是在頂點的不同的-着色數目,是關於的多項式。

例如當圖為一點時,

例子

特殊圖的色多項式
完全圖
佩特森圖

性質

給定階圖,色多項式是關於的多項式,且滿足以下性質[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).