6.7. グラフの彩色に関する練習問題
目次
グラフの彩色に関しては様々な興味深い事実が知られている。適切でない彩色についても言えることがある:
練習問題 6.9
\(G=\left( V,E\right) \) を単純グラフとする。
条件「任意の頂点 \(v \in V\) に対して、\(v\) と同じ色を持つ \(v\) の隣接頂点の個数は \(\dfrac{1}{2}\deg v\) 以下である」を満たす \(G\) の \(2\)-彩色 \(f\) が存在すると示せ。
練習問題 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\)-彩色が存在することを示せ。