彩色多項式と彩色数 : ランダムなグラフの例

Graph :

 0 0 0 1 0 1 1 1 1
 0 0 0 1 1 0 0 1 0
 0 0 0 1 0 1 0 1 1
 1 1 1 0 1 0 0 1 1
 0 1 0 1 0 1 1 1 0
 1 0 1 0 1 0 0 0 1
 1 0 0 0 1 0 0 1 0
 1 1 1 1 1 0 1 0 1
 1 0 1 1 0 1 0 1 0

Chromatic Polynomial :

X^9 - 21 X^8 + 195 X^7 - 1041 X^6 + 3474 X^5 - 7368 X^4 + 9614 X^3 
- 6978 X^2 + 2124 X

= (X) (X - 1) (X - 2) (X - 3)^2 (X^4 - 12 X^3 + 58 X^2 - 132 X + 118)

Chromatic Number = 4