【６】彩色多項式

頂点の数がｎのグラフの頂点をλ色で塗り分けることを考える．ただし隣り合う頂点は異なる色を塗るものとする．可能な塗り分けの総数はｎ次多項式として表されることを，バーコフが示した．この多項式Ｐ（λ）を彩色多項式という．タットは三角形分割された頂点数ｎの平面グラフのどの彩色多項式PGもφ^2に近い根をもつことを示しました．

PG（φ^2）<φ5-n

φ^2は5番目のベラハ数

ベラハ数Bn=2+2cos(2π/n),n=1,2,・・・

は彩色多項式の根と関係があり，具体的に書くと4,0,1,2,φ^2,3,3.2469,・・・となる．x^3-5x^2+6x-1=0のひとつの根3.2469・・・は7番目のベラハ数であるが，タットはこれを銀の比と呼んだ．φ^2＝２．１６１８・・・が黄金比と関係しているからであろう．三角形分割された頂点数ｎの平面グラフの彩色多項式のある根は，この値に近い値をとる．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝

［Ｑ］ｎ枚の壁をもつ美術館を警備するのに最低何人の警備員が必要だろうか？　（フバータルの問題）

　フバータルの問題に対するフィスクの解答「美術館定理」は単純で美しいものであった（１９７８年）．

［１］領域を三角形分割する．

［２］三角形の頂点を３色で塗り分けて，それぞれの三角駅の頂点に３色すべてが使われるようにする．

［３］使われた数が最も少ない色を指定し，そこに警備員を配置する．

［Ａ］　［ｎ／３］人．

［Ｑ］ｎ枚の直角壁をもつ美術館を警備するのに最低何人の警備員が必要だろうか？

［Ａ］　［ｎ／４］人．直角美術館はすべて凸四角形分割をもつ．ガウス記号中の４は四角形分割に関係している．

＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝＝