頂点彩色と彩色数

彩色数 $χ (G)$ を、上下からの評価を合わせて求められる。上からは彩色を構成して評価し、下からはクリークの大きさ $ω (G)$ ・ $⌈ ∣ V ∣/ α (G)⌉$ ・奇閉路で評価する。クネーザーグラフの彩色数は、ロヴァースの定理 $χ (K (n, k)) = n - 2 k + 2$ （ $n \geq 2 k$ ）を引用して求められる

前提

2 部グラフと奇閉路（大学数学グラフ理論）
最大独立集合と最小頂点被覆（大学数学グラフ理論）

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

算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）

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

説明

グラフの頂点に色を塗り、辺で結ばれた 2 頂点が必ず違う色になるようにする塗り方を「彩色」といいます。使う色の数の最小値が彩色数 $χ (G)$ です。この技能では、実際に塗って $χ (G)$ を上から押さえ、クリーク・独立数・奇閉路を使って下から押さえます。両方が一致すれば $χ (G)$ が決まります。時間割の衝突回避、周波数の割り当て、レジスタ割り当てなど、「ぶつかるもの同士を別のグループに分ける」問題でグループ数の最小値を求めるときに使います。

なぜそうしてよいのか

グラフ $G = (V, E)$ の各頂点に色（ $1, 2, \dots, k$ の番号）を割り当て、どの辺 $uv$ についても $u$ と $v$ の色が異なるとき、これを $k$ 彩色といいます。 $k$ 彩色が存在する最小の $k$ が彩色数 $χ (G)$ です。 $k$ 彩色を 1 つ具体的に作れば、それだけで $χ (G) \leq k$ がいえます。これが上からの評価です。一方、 $χ (G) \geq m$ を示すには「どう塗っても $m - 1$ 色では足りない」ことを示す必要があり、そのために次の 3 つの理由を使います。

(1) クリーク：どの 2 頂点も辺で結ばれた頂点集合をクリークといい、その最大の大きさを $ω (G)$ と書きます。クリーク内の頂点はすべて互いに異なる色にしなければならないので、 $χ (G) \geq ω (G)$ です。(2) 独立数：同じ色の頂点同士は辺で結ばれないので、1 つの色の頂点の集まり（色クラス）は独立集合です。したがって各色クラスの大きさは $α (G)$ 以下です。 $χ (G)$ 個の色クラスで $V$ 全体を覆うので $∣ V ∣ \leq χ (G) α (G)$ 、つまり $χ (G) \geq ∣ V ∣/ α (G)$ が成り立ちます。 $χ (G)$ は整数なので $χ (G) \geq ⌈ ∣ V ∣/ α (G)⌉$ です（ $⌈ x ⌉$ は $x$ 以上の最小の整数）。(3) 奇閉路： $χ (G) \leq 2$ であることは、2 色で塗り分けられること、すなわち 2 部グラフであることと同じです。「2 部グラフ $⟺$ 奇数長の閉路をもたない」ので、奇閉路を 1 つ見つければ $χ (G) \geq 3$ です。なお、辺が 1 本でもあれば $χ (G) \geq 2$ です。

クネーザーグラフ $K (n, k)$ は、 ${1, \dots, n}$ の $k$ 元部分集合を頂点とし、互いに交わらない（共通部分が空の）2 つの部分集合を辺で結んだグラフです。上からの評価は次の塗り方で得られます。最小の要素が $i \leq n - 2 k + 1$ である部分集合には色 $i$ を塗り、残りの部分集合（ ${n - 2 k + 2, \dots, n}$ の $2 k - 1$ 個の要素だけからなるもの）にはすべて色 $n - 2 k + 2$ を塗ります。同じ色 $i$ の部分集合はどれも $i$ を含むので互いに交わります。また $2 k - 1$ 個の要素の中から選んだ 2 つの $k$ 元集合は、要素数の合計が $2 k > 2 k - 1$ なので必ず交わります。よって $χ (K (n, k)) \leq n - 2 k + 2$ です。逆向きの不等式は初等的な議論では示せず、位相的な方法で証明されたロヴァースの定理によって等号 $χ (K (n, k)) = n - 2 k + 2$ （ $n \geq 2 k$ ）が成り立ちます。これは引用して使ってかまいません。

手順

上から評価する：実際に $k$ 色で塗り、すべての辺の両端が異なる色であることを確かめて $χ (G) \leq k$ とする（同じ色の頂点の集まりが独立集合になっていればよい）
下から評価する（クリーク）：最大クリークを探して $χ (G) \geq ω (G)$ を得る
下から評価する（独立数）： $α (G)$ を求め、 $χ (G) \geq ⌈ ∣ V ∣/ α (G)⌉$ を得る
下から評価する（奇閉路）：奇数長の閉路があれば $χ (G) \geq 3$ とする
上の評価と下の評価の最大値が一致すれば、それが $χ (G)$ である。一致しなければ、塗り方を改良するか、別の下界の理由を探す
クネーザーグラフ $K (n, k)$ で $n \geq 2 k$ のときは、ロヴァースの定理 $χ (K (n, k)) = n - 2 k + 2$ を引用してよい

例題

ペテルセングラフ $P$ （ ${1, 2, 3, 4, 5}$ の 2 元部分集合 10 個を頂点とし、共通部分が空である 2 つの部分集合を辺で結んだグラフ）の彩色数 $χ (P)$ を求めよ。

例題の解答

【手順 1：上からの評価】1 を含む 4 個の部分集合 ${1, 2}, {1, 3}, {1, 4}, {1, 5}$ に色 1 を塗る。これらはどれも 1 を共有するので、互いに辺で結ばれない。残りのうち 2 を含む ${2, 3}, {2, 4}, {2, 5}$ に色 2 を塗る（どれも 2 を共有する）。最後の ${3, 4}, {3, 5}, {4, 5}$ は 3 元集合 ${3, 4, 5}$ の 2 元部分集合なので、どの 2 つも交わる。これらに色 3 を塗る。各色クラスが独立集合なので正しい 3 彩色であり、 $χ (P) \leq 3$ である。
【手順 4：奇閉路による下からの評価】 ${1, 2} - {3, 4} - {1, 5} - {2, 3} - {4, 5} - {1, 2}$ は、隣り合う集合がどれも交わらないので長さ 5 の閉路である。奇閉路があるので $P$ は 2 部グラフではなく、 $χ (P) \geq 3$ である。（手順 3 でも同じ結論になる。 $α (P) = 4$ なので $χ (P) \geq ⌈ 10/4 ⌉ = 3$ 。一方、 $P$ には三角形がなく $ω (P) = 2$ なので、手順 2 のクリークの評価だけでは足りない。）
【手順 5】上下の評価がともに 3 で一致するので $χ (P) = 3$ である。
【手順 6 による確認】 $P = K (5, 2)$ なので、ロヴァースの定理から $χ = 5 - 2 \cdot 2 + 2 = 3$ となり、上の結果と一致する。

答え: $3$

よくある誤り

最大クリークの大きさを彩色数と思い込む誤り。 $χ (G) \geq ω (G)$ は下界にすぎず、等号は一般には成り立たない。たとえば 5 頂点の閉路 $C_{5}$ は $ω (C_{5}) = 2$ だが、奇閉路なので $χ (C_{5}) = 3$ である。
独立数による下界で切り捨てをしてしまう誤り。ペテルセングラフで $∣ V ∣/ α = 10/4 = 2.5$ から「 $χ \geq 2$ 」とするのは弱すぎる。 $χ$ は整数なので、正しくは $χ \geq ⌈ 2.5 ⌉ = 3$ である。
塗り方を 1 つ見つけただけで彩色数を決めてしまう誤り。「4 色で塗れたから $χ (G) = 4$ 」は誤りで、分かるのは $χ (G) \leq 4$ だけである。等号をいうには、クリーク・ $⌈ ∣ V ∣/ α ⌉$ ・奇閉路などで $χ (G) \geq 4$ を別に示す必要がある。
ロヴァースの定理を条件の外で使う誤り。公式 $n - 2 k + 2$ が成り立つのは $n \geq 2 k$ のときだけである。 $n < 2 k$ では 2 つの $k$ 元部分集合が必ず交わるので辺がなく、 $χ (K (n, k)) = 1$ になる。たとえば $n = 4, k = 3$ に公式を当てはめると $0$ となって誤り。また、 $n - 2 k + 1$ と 1 だけずらして覚える誤りにも注意する（ $K (5, 2)$ は 3 であり 2 ではない）。

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

入口の問題

この技能を使う問題

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

彩色多項式（大学数学離散数学・組合せ論）