■完全グラフと同色の三角形(その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)
が成り立つ.
===================================