彩色多項式

削除縮約公式 $P_{G} (k) = P_{G - e} (k) - P_{G / e} (k)$ や、木 $k (k - 1)^{n - 1}$ ・閉路 $(k - 1)^{n} + (- 1)^{n} (k - 1)$ ・完全グラフ $k (k - 1) \dots (k - n + 1)$ などの基本形、頂点を順に塗る積の法則を使って、グラフの彩色多項式 $P_{G} (k)$ を求められる

前提

頂点彩色と彩色数（大学数学グラフ理論）

この技能までの道筋（9 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

樹形図で数え上げる（算数場合の数）
積の法則と和の法則（算数場合の数）
和の法則・積の法則と樹形図（数学A 場合の数と確率）
順列・円順列・重複順列（数学A 場合の数と確率）
組合せ（数学A 場合の数と確率）
グラフの次数と握手補題（大学数学グラフ理論）
2 部グラフと奇閉路（大学数学グラフ理論）
最大独立集合と最小頂点被覆（大学数学グラフ理論）
頂点彩色と彩色数（大学数学グラフ理論）

説明

彩色多項式 $P_{G} (k)$ は、グラフ $G$ の頂点を $k$ 色 ${1, 2, \dots, k}$ で塗り分ける方法の数です。条件は「隣接する 2 頂点は異なる色」だけで、 $k$ 色すべてを使う必要はなく、色には区別があります。これが求まると、 $P_{G} (k) > 0$ となる最小の正の整数 $k$ として彩色数 $χ (G)$ も読み取れます。計算には、木・閉路・完全グラフなどの基本形、頂点を順に塗る積の法則、辺を 1 本ずつ減らす削除縮約公式を組み合わせます。

なぜそうしてよいのか

積の法則が使える場合。 頂点を $v_{1}, v_{2}, \dots, v_{n}$ の順に塗るとします。 $v_{i}$ の隣接頂点のうち、すでに塗った $m_{i}$ 個が互いにすべて隣接している（クリークをなす）とします。このときそれらは必ず相異なる $m_{i}$ 色で塗られているので、 $v_{i}$ の色の選び方はそれまでの塗り方によらず常に $k - m_{i}$ 通りです。積の法則より $P_{G} (k) = \prod_{i} (k - m_{i})$ となります。
- 木（ $n$ 頂点）の場合: 木は連結なので、1 頂点 $v_{1}$ を根とし、すでに塗った頂点に辺でつながる頂点を 1 つずつ加えていく順（根から外へ広げる順）で塗れます。新しく塗る頂点が塗り済みの頂点 2 個と隣接していたとすると、その 2 個は塗り済みの部分の中で道で結ばれているので閉路ができてしまいます。したがって $v_{1}$ 以外の各頂点は、塗り済みの頂点とちょうど 1 本の辺でつながります。よって $m_{i} = 1$ （ $i \geq 2$ ）となり、 $P (k) = k (k - 1)^{n - 1}$ です。
- 完全グラフ $K_{n}$ の場合: どの順でも $m_{i} = i - 1$ なので、 $k (k - 1) \dots (k - n + 1)$ です。
- 互いにつながっていない部分に分かれるグラフでは、各部分を独立に塗れるので、積の法則より各部分の彩色多項式の積になります。

削除縮約公式。 辺 $e = uv$ を取り除いたグラフを $G - e$ とします。 $u$ と $v$ を 1 頂点にまとめ、両者の隣接頂点をすべてその頂点に隣接させたグラフを $G / e$ とします（このときできるループは消し、多重辺は 1 本にまとめます）。 $G - e$ の正しい塗り方は、次の 2 種類にちょうど分かれます。
- $u, v$ が異なる色のもの: これは $G$ の正しい塗り方そのものです。
- $u, v$ が同じ色のもの: まとめた頂点にその色を塗れば、 $G / e$ の正しい塗り方と 1 対 1 に対応します。

和の法則より $P_{G - e} (k) = P_{G} (k) + P_{G / e} (k)$ 、すなわち $P_{G} (k) = P_{G - e} (k) - P_{G / e} (k)$ です。辺のないグラフは $k^{n}$ で、公式を使うたびに辺か頂点が減ります。よって $P_{G} (k)$ は $k$ の多項式になります。

閉路 $C_{n}$ （ $n \geq 3$ ）の場合。 $P_{C_{n}} (k) = (k - 1)^{n} + (- 1)^{n} (k - 1)$ を $n$ についての帰納法で示します。
- 基底 $n = 3$ : $C_{3} = K_{3}$ なので $P_{C_{3}} = k (k - 1) (k - 2)$ です。一方、 $(k - 1)^{3} - (k - 1) = (k - 1) {(k - 1)^{2} - 1} = (k - 1) \cdot k (k - 2)$ となり、一致します。
- ステップ $n \geq 4$ : $C_{n - 1}$ で公式が成り立つと仮定します。 $C_{n}$ の 1 辺を削除すると $n$ 頂点の道（木）になり、その辺を縮約すると $C_{n - 1}$ になります（ $n - 1 \geq 3$ なので単純な閉路です）。よって $P_{C_{n}} = k (k - 1)^{n - 1} - {(k - 1)^{n - 1} + (- 1)^{n - 1} (k - 1)}$ です。ここで $k (k - 1)^{n - 1} - (k - 1)^{n - 1} = (k - 1)^{n - 1} (k - 1) = (k - 1)^{n}$ であり、 $- (- 1)^{n - 1} (k - 1) = (- 1)^{n} (k - 1)$ です。したがって $P_{C_{n}} = (k - 1)^{n} + (- 1)^{n} (k - 1)$ となり、 $C_{n}$ でも公式が成り立ちます。

手順

基本形かどうかを確認する。木なら $k (k - 1)^{n - 1}$ 、閉路 $C_{n}$ なら $(k - 1)^{n} + (- 1)^{n} (k - 1)$ 、完全グラフ $K_{n}$ なら $k (k - 1) \dots (k - n + 1)$ を使う。互いにつながっていない部分に分かれるときは、各部分の彩色多項式の積をとる。
塗る順序を工夫して積の法則を使う。各頂点について、すでに塗った隣接頂点 $m$ 個が互いに隣接しているなら、選択肢は $k - m$ 通りである。この条件が全頂点で成り立つ順序があれば、それらの積が答えになる。なお、 $G$ が弦のない長さ 4 以上の閉路（閉路上の頂点どうしを結ぶ辺が閉路の辺以外にないもの）を含むと、この順序は存在しない。その閉路上で最後に塗る頂点では、塗り済みの 2 隣接頂点が隣接していないからである。
手順 1・2 が使えないときは辺 $e = uv$ を 1 本選び、 $P_{G} (k) = P_{G - e} (k) - P_{G / e} (k)$ で分解する。 $G - e$ と $G / e$ がどちらも基本形や積の法則で求まる形になる辺を選ぶとよい。
$G / e$ を作るときは、 $u, v$ を 1 頂点にまとめ、 $u$ と $v$ 両方の隣接頂点をすべて引き継ぐ。ループは消し、重なった辺は 1 本にまとめる。頂点数は $1$ 減る。
展開・因数分解して整理し、検算する。 $n$ 頂点・辺数 $∣ E ∣$ のグラフでは、最高次の項は $k^{n}$ 、 $k^{n - 1}$ の係数は $- ∣ E ∣$ になる。また $k < χ (G)$ の正の整数 $k$ では値が $0$ になる。

例題

頂点 $a, b, c, d, e$ と辺 $ab, b c, c d, d e, e a, a c$ からなるグラフ $G$ （5 頂点の閉路 $a - b - c - d - e - a$ に弦 $a c$ を 1 本加えたもの）の彩色多項式 $P_{G} (k)$ を求めよ。

例題の解答

手順 1. $G$ は閉路 $C_{5}$ に辺が 1 本多いので、木でも閉路でもありません。 $b d$ などが辺でないので、完全グラフでもありません。また $G$ は連結です。よって基本形には当てはまりません。

手順 2. $a - c - d - e - a$ は長さ 4 の閉路で、 $a d$ も $ce$ も辺ではないので弦がありません。どの順で塗っても、この 4 頂点のうち最後に塗る頂点では、閉路上の 2 つの隣接頂点がすでに塗られていて、しかも互いに隣接していません。たとえば $d$ が最後なら、 $c$ と $e$ が塗り済みで非隣接です。このとき選択肢の数は $c, e$ が同色かどうかで変わるので、手順 2 の順序は存在しません。

手順 3. そこで削除縮約公式を使います。弦 $e_{0} = a c$ を選ぶと $P_{G} (k) = P_{G - e_{0}} (k) - P_{G / e_{0}} (k)$ です。 $G - e_{0}$ は閉路 $C_{5}$ なので、手順 1 の公式より $P_{G - e_{0}} (k) = (k - 1)^{5} - (k - 1)$ です。

手順 4. $a$ と $c$ をまとめた頂点を $w$ とします。 $a$ の隣接頂点 $b, e$ と $c$ の隣接頂点 $b, d$ をすべて引き継ぐので、 $w$ は $b, d, e$ と隣接します。辺 $w b$ は 2 本重なりますが 1 本にまとめ、辺 $a c$ からできるループは消します。残る辺 $d e$ も加えると、 $G / e_{0}$ は三角形 $w, d, e$ に頂点 $b$ が $w$ だけにつながった形です。これは手順 2 で $w, d, e, b$ の順に塗れるので、 $P_{G / e_{0}} (k) = k (k - 1) (k - 2) (k - 1)$ です。

よって
$P_{G} (k) = (k - 1)^{5} - (k - 1) - k (k - 1)^{2} (k - 2) = (k - 1) {(k - 1)^{4} - 1 - k (k - 1) (k - 2)}$
です。ここで $(k - 1)^{4} - 1 = {(k - 1)^{2} - 1} {(k - 1)^{2} + 1} = k (k - 2) (k^{2} - 2 k + 2)$ なので、波かっこの中は $k (k - 2) {(k^{2} - 2 k + 2) - (k - 1)} = k (k - 2) (k^{2} - 3 k + 3)$ となります。したがって
$P_{G} (k) = k (k - 1) (k - 2) (k^{2} - 3 k + 3)$
です。

手順 5（検算）. 展開すると $k^{5} - 6 k^{4} + 14 k^{3} - 15 k^{2} + 6 k$ です。 $k^{4}$ の係数 $- 6$ は辺数 6 と一致します。また $P_{G} (2) = 0$ 、 $P_{G} (3) = 3 \cdot 2 \cdot 1 \cdot 3 = 18 > 0$ なので $χ (G) = 3$ で、三角形 $ab c$ を含むことと整合します。

答え: $k (k - 1) (k - 2) (k^{2} - 3 k + 3)$

よくある誤り

削除縮約公式の符号を $P_{G} = P_{G - e} + P_{G / e}$ としてしまう誤り。正しくは $P_{G} (k) = P_{G - e} (k) - P_{G / e} (k)$ 。辺を加えると制約が増えて塗り方は減るので、引き算になる（和になるのは $P_{G - e} = P_{G} + P_{G / e}$ のほう）。
塗り済みの隣接頂点が互いに隣接していないのに、選択肢を $k - m$ 通りとしてしまう誤り。たとえば $C_{4}$ を周に沿って $a, b, c, d$ の順に塗り、 $k (k - 1) (k - 1) (k - 2)$ とするのは誤り（ $a$ と $c$ が同色なら $d$ は $k - 1$ 通りになる）。正しくは $(k - 1)^{4} + (k - 1) = k (k - 1) (k^{2} - 3 k + 3)$ 。
色の区別をなくしたり、「ちょうど $k$ 色を使う」塗り方だけを数えたりしてしまう誤り。たとえば三角形の 3 色での塗り方を $1$ 通りとするのは誤り。 $P_{K_{3}} (k)$ は使わない色があってもよく、色に区別がある数え方なので、正しくは $P_{K_{3}} (3) = 3 \cdot 2 \cdot 1 = 6$ 。
縮約で片方の頂点の隣接しか引き継がなかったり、重なった辺を 2 本のまま扱ったりする誤り。例題で $w$ と $d$ の辺を落とすと、 $G / e_{0}$ を道 $b - w - e - d$ とみて $k (k - 1)^{3}$ としてしまう。正しくは $w$ が $b, d, e$ すべてと隣接し、 $P_{G / e_{0}} = k (k - 1)^{2} (k - 2)$ 。多重辺は塗り分けの条件としては 1 本と同じである。

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

入口の問題

この技能を使う問題

この技能の次に学べること

ボンド束と彩色多項式（大学院数学代数的組合せ論）