特殊圖的色多項式
完全圖 |
|
樹 |
|
環 |
|
佩特森圖 |
|
給定階圖,色多項式是關於的多項式,且滿足以下性質[1]:
- 多項式的次數為。
- 的係數為1。
- 的係數為。
- 的係數不為0且正負交替出現。
特別的,設有個連通分量,分別為,那麼
- 的係數為0。
給定圖與,那麼
其中代表邊收縮:令所連接的兩個頂點計為和,而邊收縮會使頂點和合併成一個新的頂點,並使原本與和相連的所有邊都連到。
證明[2] 假設所連接的兩個頂點為和,考慮圖。
- 當和的顏色相同時,這種着色方式也是的一種合理着色方式,反之亦然。所以對圖將和染上相同顏色的着色方式有種。
- 當和的顏色不同時,這種着色方式也是的一種合理着色方式,反之亦然。所以對圖將和染上不同顏色的着色方式有種。
所以圖的不同着色方式數目為
Whitney, Hassler, The coloring of graphs, Annals of Mathematics (JSTOR), 1932: 688–718
劉儒英. 关于图的色多项式. 青海師範大學學報(自然科學版). 1986, (Z1) [2015-03-07]. (原始內容存檔於2019-06-16).