グラフ理論の問題

頂点集合を $V=\{0,1,2,3,4,5,6\}$ とし、相異なる 2 頂点 $i,j$ を、$i-j$ を $7$ で割った余りが $2,3,4,5$ のいずれかであるときに限り辺で結んだ単純無向グラフを $G$ とする。言い換えると、$i,j$ が辺で結ばれるのは $i-j\equiv \pm 2$ または $i-j\equiv \pm 3(\mathrm{mod}7)$ のときに限る。$G$ の彩色数 $\chi (G)$（隣接する頂点が異なる色になるように頂点を塗るのに必要な色の最小数）と、辺彩色数 ${\chi }^{\prime }(G)$（端点を共有する辺が異なる色になるように辺を塗るのに必要な色の最小数）を、この順に組 $(\chi (G),{\chi }^{\prime }(G))$ で答えよ。

各部集合がちょうど $3$ 個の頂点からなる完全 $3$ 部グラフを $G=K_{3,3,3}$ とする。すなわち $G$ は、頂点集合 $V=A\cup B\cup C$（$A,B,C$ は互いに素で、それぞれ $3$ 個の頂点からなる）をもち、異なる部集合に属する 2 頂点はすべて辺で結ばれ、同じ部集合に属する 2 頂点は辺で結ばれない単純グラフである。

$G$ の彩色数 $\chi (G)$ と辺彩色数 ${\chi }^{\prime }(G)$ を求め、組 $(\chi (G),{\chi }^{\prime }(G))$ の形で答えよ。ここで辺彩色数とは、端点を共有する 2 辺が異なる色になるように全ての辺を塗るのに必要な色の数の最小値である。

$n\ge 5$ を整数とする。頂点集合を $V_n=\{0,1,2,\dots ,n-1\}$ とし、相異なる 2 頂点 $i,j$ を
$$j-i\equiv \pm 1\text{または}j-i\equiv \pm 2(\mathrm{mod}n)$$
のときに限り辺で結んだ単純無向グラフを $G_n$ とする（閉路 $C_n$ の 2 乗グラフ）。$G_n$ の彩色数（隣接する頂点が異なる色になるように頂点を塗るのに必要な最小の色数）を $\chi (G_n)$、辺彩色数（同じ頂点を端点にもつ辺が異なる色になるように辺を塗るのに必要な最小の色数）を ${\chi }^{\prime }(G_n)$ とする。
$$S=\sum _{n=5}^{12}(\chi (G_n)+{\chi }^{\prime }(G_n))$$
の値を求めよ。

集合 $[7]=\{1,2,3,4,5,6,7\}$ の 3 元部分集合全体を頂点集合とし、2 つの頂点（3 元部分集合）$A,B$ を $A\cap B=\varnothing$ のときに限り辺で結んだ単純グラフ（クネーザーグラフ $K(7,3)$）を $G$ とする。$G$ の彩色数 $\chi (G)$ と辺彩色数 ${\chi }^{\prime }(G)$ をこの順に求めよ。

頂点集合を $V=\{(i,j)\mid i\in \{1,2,3,4\},j\in \{1,2,3,4,5\}\}$ とし、相異なる 2 頂点 $(i,j),(i^{\prime },j^{\prime })$ を $|i-i^{\prime }|+|j-j^{\prime }|=1$ のときに限り辺で結んだ単純無向グラフを $G$ とする（$4$ 行 $5$ 列の格子グラフ）。各辺の長さを $1$ とする。

$G$ のある頂点から出発して $G$ の辺をたどり、出発した頂点に戻ってくる閉じた歩道で、$G$ のすべての辺を少なくとも 1 回ずつ通るものを考える（同じ辺や同じ頂点を何度通ってもよい）。このような閉じた歩道の長さ（通った辺の本数を、重複も含めて数えたもの）の最小値を求めよ。