離散数学・組合せ論の問題

頂点集合を $\{a,b,c,a^{\prime },b^{\prime },c^{\prime }\}$ とし、辺集合を
$$\{ab,bc,ca,a^{\prime }{b}^{\prime },b^{\prime }{c}^{\prime },c^{\prime }{a}^{\prime },a{a}^{\prime },b{b}^{\prime },c{c}^{\prime }\}$$
とする単純グラフ $G$（三角柱の頂点と辺がつくるグラフ）を考える。$k$ を正の整数とし、$k$ 色の中から各頂点に 1 色を割り当てる方法のうち、辺で結ばれた 2 頂点が必ず異なる色になるもの（適切な彩色）の個数を $P_G(k)$ とする。$P_G(k)$ を $k$ の多項式として求めよ。

$n$ を正の整数とする。頂点集合を $\{a_1,a_2,a_3,b_1,b_2,\dots ,b_n\}$ とし、辺集合を
$$\{a_i{b}_j\mid 1\le i\le 3,1\le j\le n\}\cup \{a_1{a}_2\}$$
とする単純グラフ $G$ を考える（完全二部グラフ $K_{3,n}$ に辺 $a_1{a}_2$ を 1 本加えたグラフ）。$k$ を正の整数とし、区別のつく $k$ 色を用意する。$G$ の各頂点に $k$ 色のいずれか 1 色を塗り、辺で結ばれた 2 頂点が必ず異なる色になるようにする（使わない色があってもよい）。このような塗り方の総数、すなわち $G$ の彩色多項式 $P(G,k)$ を $k$ と $n$ の式で求めよ。

頂点集合を $\{a,b,c,d\}$、辺集合を $$\{ab,bc,cd,da,ac\}$$ とする単純グラフ $G$ を考える。$G$ は長さ $4$ の閉路 $abcd$ に対角線 $ac$ を 1 本加えたグラフである。$k$ を正の整数とし、$G$ の頂点を $k$ 色以下で塗り分ける方法の数を $P_G(k)$ とする。ここで「塗り分ける」とは、辺で結ばれた 2 頂点が異なる色になるように、各頂点に $k$ 色のうちの 1 色を割り当てることであり、色は区別する（使わない色があってもよい）。彩色多項式 $P_G(k)$ を $k$ の式で求めよ。

頂点集合を $\{a,b,c,d\}$ とし、辺集合を
$$\{ab,bc,cd,da,ac\}$$
とする単純グラフ $G$（正方形 $abcd$ に対角線 $ac$ を加えたグラフ）を考える。$k$ を正の整数とし、$k$ 色以下を使って $G$ の各頂点に色を塗る。辺で結ばれた $2$ 頂点が必ず異なる色になる塗り方の総数を $P_G(k)$ とする（色は区別し、使わない色があってもよい）。彩色多項式 $P_G(k)$ を $k$ の式で求めよ。

頂点集合を $\{a,b,c,d\}$ とし、辺集合を
$$\{ab,bc,cd,da,ac\}$$
とする単純グラフ $G$ を考える。$k$ を正の整数とする。区別のつく $k$ 色を使い、辺で結ばれた 2 頂点が異なる色になるように $G$ の各頂点を塗る方法の数（すべての色を使う必要はない）を $P_G(k)$ とする。$P_G(k)$ を $k$ の式で表せ。