n角形の頂点をt色以下で塗り分けるグラフ彩色

質問

http://ja.wikipedia.org/wiki/%E3%82%B0%E3%83%A9%E3%83%95%E5%BD%A9%E8%89%B2
によると、
隣接する頂点同士が同じ色にならないように全頂点に彩色する問題を頂点彩色という。
彩色多項式とは、与えられたグラフをt色以下で彩色したときの彩色の組合せ数を求める式である。

閉路グラフC_n(つまり、n角形)をt色以下で彩色したときの彩色多項式は、
(t-1)^n+(-1)^n*(t-1)

これがどのように示されるのかがわからないので、どうか教えていただけないでしょうか。

回答No.2

graphaffine · ベストアンサー

>もし、正多角形の塗りわけで、隣り合う色が異なり、回転して同じ配色になると同じとみなす、ものの場合の数の公式や理論がありましたら紹介いただけるとありがたいです。

残念乍、関連する文献は存じません。が、単純に考えれば正n角形の360/n度の回転から生成される巡回群は、自然に正n角形に作用しますので、P(C[n],t)/nで求められるような気がするんですが。

なお、正方形に関しては、昔対称軸による折り返しまで含めて似たようなことを考えたことがあります。その場合は、４次の二面体群D４の自然な作用を考えることになるので、P(C[4],t)/8が求める結果でした。
nが大きい場合は、対称軸が増えるので結構ややこしくなりそうですね。

お礼

ご返答ありがとうございます。
例えば、正方形の頂点を、r(赤)、b(青)、y(黄)の3色以下で配色するとき、
隣り合う色が異なり、回転して同じ配色になっても異なるとみなす、ものの場合の数は、n=4,t=3として、(t-1)^n+(-1)^n*(t-1)=18通りとなりますが、具体的には次のようになります。
rbrb,brbr
ryry,yryr
byby,ybyb
rbry,bryr,ryrb,yrbr
brby,rbyb,bybr,ybrb
yryb,ryby,ybyr,byry

そのなかで、回転して同じ配色になっても異なるとみなすと、同じ行の彩色は同じとなり、結局6通りとなります。

ちなみに、隣り合う色の制約はなく、回転して同じ配色になっても異なるとみなす、ものの場合の数は、t=3として,t^4/4+t^2/4+t/2=24通りとなりますが、具体的には次のようになります。
rrrr,bbbb,yyyy
rrrb,rrbb,rbbb,rbrb
rrry,rryy,ryyy,ryry
bbby,bbyy,byyy,byby
rrby,rryb,rbry
bbry,bbyr,brby
yyrb,yybr,yryb

環指標(cycle index)という概念を非可換にすれば、隣り合う色が異なり、回転して同じ配色になると同じとみなす、ものの場合の数が求められる気がするのですが、よくわからないです。

回答No.1

graphaffine

dfhsdsさん、今晩は。結構長いので概略に留めます。
詳細は、下記文献を参照してください。

グラフGの色数tの彩色多項式をP(G,t)と書くことにする。
Gの一つの辺をeとするとき、P(G,t)=P(G-e,t)-P(G/e,t)　(**)が成り立つ。但し、G/eはeによる縮約。
C[n]をn-サイクルとするとき、C[n]/e＝C[n-1]、また、M=C[n]-eは長さn-1の道であり、このとき、P(M,t)=t(t-1)^(n-1)である。
よって、(**)より、P(C[n],t)=P(C[n]-e,t)-P(C[n]/e,t)=t(t-1)^(n-1)-P(C[n-1],t)である。
C[n-1]もサイクルだから、同様にしてP(C[n],t)=t(t-1)^(n-1)-t(t-1)^(n-2)+P(C[n-2],t)となる。以下、同様。

参考文献　グラフの不変数(組合せ論演習3)　　秋山仁、榎本彦衛著　東海大学出版会
51ページの問題2.39

お礼

ご回答まことにありがとうございます。
漸化式を考えるのだろうとは思いながら、予備知識がない自力では難しいと感じていました。
あとでじっくりと拝読したいと思います。

僕は、組合せ論の方面から、正多角形や正多面体の塗りわけ（ただし、隣り合う色が同じでも良い。回転して同じ配色になるものは同じとみなす）に興味を持って、それはポリアの定理と呼ばれるもので解けることを最近知りました。

今回、投稿させていただいた正多角形の塗りわけは、隣り合う色が異なり、回転して同じ配色になっても異なるとみなす、ものです。

もし、正多角形の塗りわけで、隣り合う色が異なり、回転して同じ配色になると同じとみなす、ものの場合の数の公式や理論がありましたら紹介いただけるとありがたいです。