2005 年度 冬学期 離散情報論

2005 年 10 月 17 日

Lecture 2 (辺彩色 2)
教員: 岩田 覚 助教授

文責: 堀越 保徳

本講義では主に離散最適化に関する話題を扱う. 教科書は [2] である.

1

単純グラフの辺彩色
無向グラフ G = (V, E) の各辺 e ∈ E に色を割り当てることをグラフの辺彩色という. この時, 端点を共有する辺に割り当てられる色は互いに異なっていることを要求する. グラフ G を辺彩色するのに必要な最小色数を γ(G) と書くこととし, G の各点における次数の最大値を ∆(G) と書くことにする.
グラフの辺彩色はグラフ理論の中では古い研究対象である. 特に, 4 色問題の解決が 3 正則 2 連結平面グラフの 3 辺彩色可能性と等価であることが指摘されており, 歴史的にも重要なテーマであった.
一般のグラフ G において, 不等式∆(G) ≤ γ(G)は自明である. G が二部グラフの場合は, 上の不等式が等式で成り立つ (Lecture 1, 定理 1) のに対し, 一般のグラフでは ∆(G) < γ(G) となるものが存在する. しかし, G が単純グラフの場合には, 次の結果が知られている.
定理 1 (Vizing [3, 4]). 任意の単純グラフ G に対して ∆(G) ≤ γ(G) ≤ ∆(G) + 1 が成り立つ.
この定理の証明のために, まず以下の補題を証明する [2, §28.1].
補題 2. 単純グラフ G において, 点 v 及び v に隣接する任意の点の次数は k 以下であり, 次数が丁度 k となる隣接点は高々一つであるとする. この時, G − v が k 辺彩色可能ならば, G も k 辺彩色可能である.
証明 . k に関する帰納法で証明する. k = 0 の場合は明らか. 点 v に隣接する頂点のうち丁度 1 点の次数が kで, その他の隣接点の次数は k − 1 であると仮定しても構わない. なぜならば, そうでないときには, 必要なだけ新たな点と辺を導入して次数を調整することが出来るからである.
仮定により G − v は k 辺彩色可能である. G − v の k 辺彩色に対して, Xi (i = 1, 2, . . . , k) を v に隣接するP点で色 i の辺が接続していないものの集合とする. ここで, ki=1 |Xi |2 を最小にする辺彩色を一つ固定する.
その辺彩色より定まる Xi (i = 1, 2, . . . , k) が, 任意の i ∈ {1, 2, . . . , k} に対して |Xi | =6 1 である場合, v に隣接していた点を考えると, 次数が k であったものは丁度一つの Xi に属し, その他は丁度二つに属しているので,kX|Xi | = 2deg(v) − 1 < 2ki=1が成り立つ. この不等式より, ある i, j が存在して |Xi | = 0, |Xj | ≥ 3 となることが分かる. ここで, G − v の辺のなかで色 i および j が割り当てられている辺全体からなる部分グラフを H とする. ある点 a ∈ Xj に注1

目して, a を含む H の連結成分を考えると, それは必ず道になる. この道に沿って色 i と j を入れ替えるとG − v の新たな辺彩色が得られるが, 新たな辺彩色は必ず元の辺彩色よりも |Xi |2 + |Xj |2 の値が小さくなり,辺彩色の選び方に矛盾する.
以上の議論により, 一般性を失うことなく Xk = {u} と仮定できる. ここで, G から辺 uv 及び色 k を持つ辺を除いて得られる部分グラフを G0 とする. G0 − v は k − 1 辺彩色可能である. また, v および v に隣接する点の G0 における点の次数は k − 1 以下であり, v に隣接している点で次数が k − 1 となるものは高々一つである. 従って, 帰納法の仮定より, G0 は k − 1 辺彩色可能である. 取り除かれた辺を G0 に戻し, 辺 uv に色k を与えれば, G の k 辺彩色が得られる.

¤補題 2 を用いて定理 1 を証明する.
証明 (定理 1). k = ∆(G) + 1 とする. G の任意の点は補題の条件を満たしている. そこで, 補題の条件を満たしながら, G から一つずつ点を取り除いて, 1 本の辺のみからなるグラフにすることが出来る. このグラフが k 辺彩色可能なことは明らかなので, 帰納的に補題 2 を適用すれば, 定理 1 が証明される.

¤上の証明の方針でアルゴリズムを設計することが可能で, グラフの最大次数を ∆, 点, 辺の数を n, m とすると, O(∆n2 ) の計算時間で ∆ + 1 色による辺彩色を求めることが出来る. ここで, 次数 ∆/2 以下の点は一般性を失うことなく 1 つの点にまとめ上げることが出来るので, ∆n = O(m) となり, 計算時間は O(nm) となることが分かる.

2完全グラフの辺彩色
前節の結果より, 任意の単純グラフ G について γ(G) = ∆(G) または, γ(G) = ∆ + 1 が成り立つことが分かる. 実は, 一般のグラフが与えられた時に γ(G) = ∆(G) が成り立つかどうかを答える問題は, NP 完全であることが知られている [1]. しかし, 特殊なクラスに属するグラフについては, γ(G) を即座に求めることが出来る場合がある. 特に完全グラフについては以下の結果が知られている.
定理 3. 完全グラフ Kn の辺彩色数 γ(Kn ) ついて,(γ(Kn ) =n − 1 (n : 偶数)n(n : 奇数)が成り立つ.
証明 . まず, 任意の n について γ(Kn ) ≤ n を示す. 完全グラフ Kn の点集合を V = {v0 , v1 , v2 , . . . , vn−1 },辺集合を E = {vi vj |0 ≤ i < j ≤ n − 1} とする. この時, 辺 vi vj に色 i + j (mod n) を割り当てると, 辺彩色になる.
次に, n が奇数の時に γ(Kn ) > n − 1 を示す. Kn が n − 1 色で塗れたとすると, Mi ∩ Mj = ∅ (i 6= j)
なるマッチング {Mi }n−2i=0 により, E = M0 ∪ M1 ∪ . . . ∪ Mn−2 となる. この時, |Mi | ≤ (n − 1)/2 なのでP|E| = |Mi | ≤ (n − 1)2 /2 となる. これは, |E| = n(n − 1)/2 > (n − 1)2 /2 に矛盾する.
最後に n が偶数の時に γ(Kn ) = n − 1 となることを示す. まず, Kn から vn−1 を除いて出来る完全グラフ

Kn−1 を上の方法により n − 1 色で辺彩色する. この時, 点 vi に接続していない色は, 2i (mod n − 1) である.
2

各 i ∈ {0, 1, . . . , n − 2} に対して wi ≡ 2i (mod n) とすると, n − 1 は奇数なので i 6= j ならば wi 6= wj となる. 従って, 辺 vn−1 vi に色 wi を割り当てれば, Kn の n − 1 辺彩色になる.

¤参考文献[1] I. Holyer: The NP-completeness of edge-coloring, SIAM Journal on Computing 10 (1981), 718–720.
[2] A. Schrijver: Combinatorial Optimization, Springer-Verlag, 2003.
[3] V. G. Vizing: Ob otsenke khromaticheskogo klassa p-grafa [Russian; On an estimate of the chromaticclass of a p-graph], Diskretnyǐ Analiz 3 (1964), 25–30.
[4] V. G. Vizing: Khromaticheskiǐ klass mul’tigrafa [Russian], Kibernetika 1965:3 (1965), 29–39 [Englishtranslation: The chromatic class of a multi graph, Cybernetics 1:3 (1965), 32–41].

3