高知大学大学院理学研究科情報科学専攻（専門）

3 以下、有限単純無向グラフを単にグラフと言う。 k 色の色によるグラフ G の点彩色の個数を P_{G}(k) で表すとき、 P_{G}(k) は k の多項式になることが知られており、これを G の彩色多項式と呼ぶ。この定義のもと、次の問に答えよ。

(1) 頂点数 n の空グラフ N_{n} の彩色多項式を求めよ。

(2) 頂点数 n の完全グラフ K_{n} の彩色多項式を求めよ。

(3) 頂点数 n の木 T の彩色多項式を求めよ。

(4) e を G の任意の辺とする。 G から e を除去して得られるグラフを H、 G から e を

縮約して得られるグラフを K とするとき

P_{G}(k) = P_{H}(k) − P_{K}(k)

が成り立つことを示せ。

(5) 頂点数 5 の車輪 W_{5} の彩色多項式を求めよ。

[figure]

3 専門受験番号