グラフ理論 #10
第10回講義 6月25日--- 地図の彩色、辺彩色、彩色多項式 ---情報科学研究科 井上純一
http://chaosweb.complex.eng.hokudai.ac.jp/~j_inoue/

地図の彩色（面彩色）k-面彩色可能 : 地図の隣接する2つの面が同じ色にならないように k 色で彩色できる場合全ての平面グラフは4-彩色可能である（4色定理、1976年計算機実験の助けを借りて証明される）※ この講義ではそれに至るまでに得られた幾つかの知見・定理について見ていく (4色定理の証明は取り上げない）

3－面彩色可能なグラフの一例

定理19・１とその証明
地図Gが2 面彩色可能であるための必要十分条件はGがオイラー・グラフであることである（証明のアウトライン）
[必要性]

R

deg(v)=3Gの各点を含む面は偶数でなければならいので、
Bdeg(v)=4各点の次数は偶数。
B「連結グラフがオイラー・グラフである条件はRGの点の次数が全て偶数」であったことを思い出せば、Gはオイラー・グラフである

BR
必ず同じ色が隣同士になってしまう[十分性]
任意の面（赤）内の点Xからスタートし、偶数回の辺と交わって到達する面を赤で、奇数回の辺と交わってR到達する面を青で彩色する
この方法で任意の点から任意の点へ戻る閉路を考えるとグラフがオイラー・グラフであれば、必ず偶数回だけ辺と交わるので2色彩色で矛盾なく、全ての面が特定される

RBRBB

定理19・2
Gはループの無い平面グラフとし、G*はGの幾何学的双対である。
このとき、Gがk 彩色可能であるための必要十分条件は、G*がk面彩色可能であることである。

（例）

3-彩色

3-面彩色

定理19・4とその証明
Gは各点が3次の地図であるとする。このとき、Gが３-面彩色可能であるための必要十分条件は各面が偶数本の辺で囲まれていることである。

(証明)
[必要性]
任意の面Fに関し、各点の次数が3であるから、Fを取り囲む面は2色で彩色可能である。そのような面は偶数個なければならないので、全ての面は偶数本の辺で囲まれている。

[十分性]「Gが単純グラフであり、Gの各面が三角形で、各点の次数が偶数（オイラー・グラフ）であれば、Gは3点彩色可能である」という双対な結果を示す。
定理1９・1より、Gの面はR、Bの2色で彩色可能
このとき 面R : α → β → γ (時計回り)

B

R

面B : α → β → γ (反時計回り)のような点彩色をグラフ全体に施せばよい。

BRRRB

辺彩色
k-辺彩色可能 : グラフGの隣接する辺は同じ色にならないように、Gの各辺をk色で彩色できるとき
彩色指数 : Gがk-辺彩色可能、k-1辺彩色不可能なとき、彩色指数を

χ ′(G ) = k彩色指数で定義する。

χ ′(G ) = 4であるグラフの一例

定理20・2とその証明 #1n(≠ 1)が奇数であれば、χ ′( K n ) = n, 偶数ならば、χ ′( K n ) = n − 1(証明)[nが奇数の場合]
完全グラフの点を正ｎ角形の形状に配置する。その外周の点を異なる色を用いて彩色し、次に残りの辺のそれぞれをそれと平行な外周の辺に用いられた色で彩色する。
このとき、同じ色で彩色できる辺の最大数は (n-1)/2従って、彩色指数が n-1 であれば11m( K n ) ≤ (n − 1) χ ′( K n ) = (n − 1) 2 ≠ n C222

矛盾。

彩色指数が n であれば11m( K n ) ≤ (n − 1) χ ′( K n ) = n(n − 1) = n C222

OK。従って彩色指数はnである

定理20・2とその証明#2[nが偶数のとき]

345

K nはK n −1と1つの点の和とみなせる。
K nはn − 1色で彩色可能。
K n −1の次数はn − 2であるから、各点には全n色のうち欠けてる色が1色ずつあるので、1

これでそれぞれの辺を彩色すればK nのn − 1彩色ができあがる
n-1彩色可能2

例題9.4(1)
彩色指数5
彩色指数3(2)(3)
彩色指数4ピータースン・グラフは全ての次数が3である3次グラフ
一般に「グラフが3次のハミルトングラフならば、その彩色指数は3である」ことが知られているが、ピータースン・グラフの彩色指数は4
従って、ピータースン・グラフはハミルトンではない。

彩色多項式
Gを単純グラフとし、k 色での点彩色の仕方がPG (k )通りあるとき、PG (k )を彩色多項式と呼ぶ(例)

PG (k ) = k (k − 1) 2

PG (k ) = k (k − 1)(k − 2)

PG (k ) = k (k − 1)n −1

定理21・1 とその適用例
単純グラフGから辺を削除して得られるグラフ
をG − eとし、縮約してできるグラフをG / eとするとPG (k ) = PG −e (k ) − PG / e (k )が成立する。
（例）

k (k − 1)(k − 2)k (k − 1)(k − 2)(k − 3)k (k − 1)(k − 2) 2

定理21・1の証明
ee=vwとする。点vと点wが異なる色になるような、G-eのk彩色の個数はvとｗを結ぶ辺を描いても変わらない。

∴ PG (k )に等しい。

点vと点wが同色になるような、G/eのk彩色の個数はvとｗを同一視しても変わらない。
従って

PG −e (k ) = PG (k ) + PG / e (k )∴ PG / e (k )に等しい。

例題9.5
どちらも木であり、彩色指数はk ( k − 1)

3PC ( k ) = k ( k − 1) − k ( k − 1) = k 4 − 4k 3 + 5k 2 − 2k3

2

4つの点を持つ単純連結グラフの彩色指数はPG (k ) = k 4 − mk 3 + ak 2 − bk

例題9.6の(1)a

この2点が同色か異色かで場合が分かれる

k

同じ色で彩色できるk-2b

完全二部グラフK 2,3の彩色法としては(1)a, bが同色の場合：k (k − 1)3(2)a, bが異色の場合:

k (k − 1)(k − 2)3k-2

k-2

k-1

これらを合わせて、結局求める彩色多項式は
PK2,3 (k ) = k (k − 1)3 + k (k − 1)(k − 2)3

例題9.6の(2)(1)での結果を一般化する。

as個の点からなる、このグループは同色で彩色できる(1)点a, bが同色の場合 : k (k − 1) sb

この2つの点が同色か異色かで場合が分かれる(2)点a, bが異色の場合 : k (k − 1)(k − 2) s
これらの合計として、求める彩色多項式は
PK2,s (k ) = k (k − 1) s + k (k − 1)(k − 2) s

例題9.6の(3)PG (k ) = PG −e (k ) − PG / e (k )

公式：

を用いる

PC4 ( k ) = k ( k − 1)3 − k ( k − 1)( k − 2) = k ( k − 1)( k 2 − 3k + 3)

C4k-1

k-1

k-1

=ek-2-kk-1

k

再帰的に現れることに注意C5=-C4PC5 (k ) = k (k − 1) 4 − PC4 (k )= k (k − 1)(k 3 − 4k + 6k − 4)

例題9.6の(4)n = 2のとき、PC2 (k ) = k (k − 1)となり、成立。

k-1

PCn−1 ( k ) = ( k − 1) n −1 + ( −1) n−1 ( k − 1)を仮定する。

k分解公式よりTnPCn (k ) = k (k − 1) n−1 − PCn−1 (k )
Cn

C n-1
=e

-

= k (k − 1) n−1 − {(k − 1) n−1 + (−1) n−1 (k − 1)}= (k − 1) n + (−1) n (k − 1)
再帰的に現れることを用いる

証明おわり。

演習問題10