■完全グラフと同色の三角形(その12)

 n角形はn−3本の対角線で,n−2個の三角形に分割することができる.この三角形分割された図形は3色(B,R,Y)を使って,隣接する2頂点がすべて異なる色になるように塗り分けることができる.たとえば,2つの頂点がRとBであったならば,もう一つの頂点はYとすればよい.また,三角形分割された平面グラフは次数が3か4か5の頂点をもつ.

===================================

 一般に,頂点数nのグラフを,接する2頂点がすべて異なる色になるようにλ色で塗り分けることを考える.可能な異なる塗り分けの総数は,多項式P(λ)で表される.P(λ)を彩色多項式という.

 タットは,三角形分割されたある平面グラフの彩色多項式

  x^3−5x^2+6x−1=0

のひとつの根は3.2469796に近いことを確かめ,この根を銀の数と読んだ.

 n→∞のとき,タットは三角形分割された平面グラフのどの彩色多項式も,

  φ^2=2.161803・・・

に近い解をもつことを示した.より正確には

  P(φ^2)≦φ^(5-n)

が成り立つ.

===================================