6.6. Vizing の定理
目次
ここまではグラフの頂点の彩色を考えてきた。グラフの辺の彩色を考えることもできる:
定義 6.6.1
\(G=\left( V,E,\varphi\right) \) を多重グラフ、\(k\) を任意の自然数とする。
\(G\) の \(k\)-辺彩色 (\(k\)-edge-coloring) とは、写像 \(f\colon E\rightarrow\left\{ 1,2,\ldots,k\right\} \) を言う。
\(k\)-辺彩色 \(f\) が適切 (proper) とは、共通の端点を持つ任意の異なる二辺が同じ色を持たないことを言う。
辺彩色に関する最も重要な事実は次の定理である:
定理 6.6.2
少なくとも一つの頂点を持つ単純グラフを \(G\) とする。\(\alpha\) を次のように定める:
\[ \alpha\colonequals \max\left\{ \deg v\mid v\in V\right\} \]
このとき \(G\) は適切な \(\left( \alpha+1\right) \)-辺彩色を持つ。
[Schrij04] などのグラフ理論に関する教科書を参照してほしい1。□
二つの点を指摘しておく:
-
Vizing の定理にある \(\alpha+1\) は一般には改善できない (\(G\) が奇数長の閉路グラフ \(C_{n}\) の場合を考えれば分かる)。
-
Vizing の定理は単純グラフだけではなく多重グラフにも適用できる。ただし、多重グラフを考えるときは \(\alpha + 1\) が \(\alpha + m\) になる: ここで \(m\) は同じ端点を結ぶ平行辺の個数の最大値と定義される。