6.7. グラフの彩色に関する練習問題

目次

グラフの彩色に関しては様々な興味深い事実が知られている。適切でない彩色についても言えることがある:

練習問題 6.9

\(G=\left( V,E\right) \) を単純グラフとする。

条件「任意の頂点 \(v \in V\) に対して、\(v\) と同じ色を持つ \(v\) の隣接頂点の個数は \(\dfrac{1}{2}\deg v\) 以下である」を満たす \(G\) の \(2\)-彩色 \(f\) が存在すると示せ。

[Remark: この問題は次のように表現されることもある: 政治家の有限集合が与えられる。一部の政治家同士は (お互いに) 敵同士である (自分自身が敵である政治家はいない。もし \(u\) が \(v\) の敵なら、\(v\) も \(u\) の敵となる。また、敵の敵は必ずしも友ではない。つまり考えているのは制約を持たない単なる単純グラフである)。この政治家の集合を二つの派閥に分割し、任意の政治家が「自分と同じ派閥に属する自分の敵の人数は、自分の敵の総数の半分以下である」を満たすようにできると示せ。]

[ヒント: \(G\) の \(2\)-彩色 \(f\) を任意に取り、条件が成り立つまで \(f\) を段階的に改変する。]

[解答: これは 2017 年春学期に開講された講義で出した homework set #0 の Exercise 1 である。解答は講義ページに載っている。]

練習問題 6.9 は複数の色がある場合に一般化できる:

練習問題 6.10

\(k\) を自然数とする。\(k\) 個の非負実数 \(p_{1},p_{2},\ldots,p_{k}\) が \(p_{1}+p_{2}+\cdots+p_{k}\geq1\) を満たすと仮定する。\(G=\left( V,E\right) \) を単純グラフとする。

条件「任意の頂点 \(v \in V\) に対して、\(v\) と同じ色を持つ \(v\) の隣接頂点は \(p_{f\left( v\right) }\deg v\) 以下である」を満たす \(G\) の \(k\)-彩色が存在することを示せ。

[解答: これは 2017 年春学期に開講された講義で出した midterm #2 の Exercise 6 である。解答は講義ページに載っている。]

広告