著色多項式

著色多項式

一個圖的全正常著色的方法數關於所用顏色數量的函式為一多項式,該多項式稱為著色多項式。

基本介紹

  • 中文名：著色多項式
  • 外文名：chromatic polynomial
  • 適用領域：圖論
  • 所屬學科：數學
定義,性質,染色多項式,

定義

給定
和圖
，
的值為全正常著色
的個數. 可用顏色的集合為
,
.
為一關於
的多項式，稱為著色多項式.

性質

著色遞歸
如果
為簡單圖且
,則
.
為圖
的邊集合，
為
刪去邊
後得到的子圖，
表示收縮
中邊
得到的圖.
次數、係數與圖的特徵
簡單圖
的著色多項式
的次數為
；次高次項係數絕對值為
；最低次項次數為
的連通分量個數；
的係數正負交替.
和色數關係
設圖
的色數為
,則
為使得
的最小的
.

染色多項式

相關詞條

熱門詞條

聯絡我們