6.4. グラフの適切な彩色に関する練習問題

\(G\) を \(n\) 頂点の単純グラフ、\(k\) を正整数とする。

次の命題を示せ:

1. \(G\) が適切な \(k\)-彩色を持つなら、\(K_{k+1}\) と同型な \(G\) の部分グラフは存在しない。

2. \(k\geq n-2\) のとき (a) の逆が成り立つ。つまり、\(K_{k+1}\) と同型な \(G\) 部分グラフが存在しないなら、\(G\) は適切な \(k\)-彩色を持つ。

3. \(k < n - 2\) のときも (a) の逆は成り立つか？ 特に、\(n=5\) かつ \(k = 2\) のとき成り立つか？

\(G\) を連結でループレスな多重グラフとする。\(G\) が適切な \(2\)-彩色を持つのは、\(G\) の任意の三頂点 \(u\), \(v\), \(w\) が次の条件を満たすとき、かつそのときに限ると示せ:

\(n\geq2k>0\) を満たす正整数 \(n\), \(k\) を固定し、\(S=\left\{ 1,2,\ldots,n\right\} \) と定める。第 2.6.3 項 で定義した \(S\) の \(k\) 次 Kneser グラフ \(K_{S,k}\) を考える。\(K_{S,k}\) が適切な \(\left( n-2k+2\right) \)-彩色を持つことを示せ。

[ヒント: 二つの \(S\) の部分集合が共通要素を持たないとき、それらの最小値 (値が最も小さい要素) について、何が言えるだろうか？ 「一つだけ存在する」は良い最初の一歩である。]

[Remark: 1978 年に Lovász はこの結果が最適だと (トポロジーを使って！) 証明した ── つまり \(K_{S,k}\) が適切な \(q\)-彩色を持つような整数 \(q\) の最小値は \(n-2k+2\) である。]

\(k\) を自然数、\(G\), \(H\) を単純グラフとする。\(G\) と \(H\) の両方が適切な \(k\)-彩色を持つとする。このとき、デカルト積 \(G\times H\) も適切な \(k\)-彩色を持つと示せ。 [デカルト積は定義 2.14.10 で定義した。]

[Remark: 逆が成り立つことは容易に示せる。つまり、\(G\times H\) が適切な \(k\)-彩色を持つとき \(G\) と \(H\) も適切な \(k\)-彩色を持つ。ただし頂点集合 \(\operatorname*{V}\left( G\right) \) と \(\operatorname*{V}\left( H\right) \) はどちらも空集合でないとする。]

\(n\) を自然数、\(G\) を例 2.1.3 で定義した \(n\) 次の共素性グラフ \(\operatorname*{Cop}\nolimits_{n}\) とする。さらに \(k\) を自然数、\(m\) を \(\left\{ 1,2,\ldots,n\right\} \) に含まれる素数の個数とするとき、次の命題を示せ:

1. グラフ \(G\) が適切な \(k\)-彩色を持つのは \(k \geq m + 1\) のとき、かつそのときに限る。

2. グラフ \(G\) が \(K_{k}\) と同型な部分グラフを持つのは \(k\leq m+1\) のとき、かつそのときに限る。

\(n\), \(k\) を正整数、\(K\) を要素数 \(k\) の集合、\(D\) を de Bruijn 有向グラフ (定理 5.16.2 の証明で構築した多重有向グラフ) とする。\(D^{\operatorname{und}}\) からループを全て除去した無向グラフを \(G\) とする。\(G\) が \(\left( k+1\right) \)-彩色を持つと示せ。

\(k\) を自然数とする。辺の個数が \(\dfrac{k\left( k+1\right) }{2}\) 未満の単純グラフが適切な \(k\)-彩色を持つと示せ。