基本介紹
- 中文名:色多項式
- 外文名:Chromatic polynomial
- 領域:數學
- 適用領域:代數圖論
定義,特殊圖的色多項式,性質,不連通圖,加邊或減邊,加點或減點,補圖,
定義
例如當圖
為一點時,
。


特殊圖的色多項式
完全圖 ![]() | ![]() |
有n個頂點的樹 ![]() | ![]() |
環圖 ![]() | ![]() |
![]() |
性質
不連通圖
若圖
是不連通圖,可分成
個連通片
,圖
的著色方法數等於所有連通片的著色方法數的乘積。





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



環圖有遞推公式:




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






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







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

