辺彩色
概要
辺彩色（edge coloring）とは、グラフの辺に色を塗って、端点を共有する 2 辺がつねに異なる色になるようにすることであり、同じ色の辺の全体はマッチングになる。必要な色の最小数を辺彩色数 $\chi'(G)$ といい、最大次数 $\Delta$ 以上で、単純グラフでは Vizing の定理により $\Delta+1$ 以下であるから、単純グラフは $\chi'=\Delta$ の第 1 類と $\chi'=\Delta+1$ の第 2 類に分かれる。二部グラフと頂点が偶数個の完全グラフは第 1 類であり、辺の多すぎるグラフ、頂点が奇数個の正則グラフ、橋をもつ 3-正則グラフ、Petersen グラフは第 2 類である。時間割や総当たり戦の日程の作成は辺彩色の問題として表される。
前提知識: 彩色, マッチング(グラフ理論), 次数(グラフ), 正則グラフ
辺彩色 は、グラフの辺に色を塗って、端点を共有する 2 辺がいつも異なる色になるようにすることである。同じ色の辺はどの 2 本も端点を共有しないので、1 つの色の辺の全体はマッチング(グラフ理論)になる。辺彩色とは、辺の全体をいくつかのマッチングに分けることにほかならない。
必要な色の最小数 $\chi'(G)$ を辺彩色数という。1 つの頂点に集まる辺はすべて異なる色を要するので $\chi'(G)$ は最大次数 $\Delta$ 以上であり、単純グラフでは $\Delta+1$ 以下であること（Vizing の定理）が知られている。したがって単純グラフは、$\chi'=\Delta$ のものと $\chi'=\Delta+1$ のものの 2 種類に分かれる。どちらに属するかの判定は易しくないが、この記事では、完全グラフの辺彩色数を決め（thm-ec-complete）、辺の多すぎるグラフや橋をもつ 3-正則グラフが $\Delta+1$ 色を要することを示し（prop-ec-overfull、cor-ec-bridge）、Petersen グラフの辺彩色数が $4$ であることを証明する（thm-ec-petersen）。
定義
この記事では、特に断らない限りグラフは有限の単純グラフとする。2 本の辺が 隣接する とは、相異なり、端点を共有することをいう。
グラフ $G=(V,E)$ と正の整数 $k$ について、写像 $c\colon E\to\{1,\dots,k\}$ で、隣接する 2 辺 $e,f$ に対してつねに $c(e)\ne c(f)$ となるものを $G$ の $k$-辺彩色（$k$-edge coloring）という。$G$ が $k$-辺彩色をもつ最小の $k$ を $G$ の 辺彩色数（chromatic index, edge chromatic number）といい、$\chi'(G)$ と書く。辺のないグラフでは $\chi'(G):=0$ とする。
これは 彩色 の記事の定義「辺彩色」で色の集合を $\{1,\dots,k\}$ にしたものである。$k$-辺彩色 $c$ について、各色の辺の全体 $c^{-1}(i)$ を 色類 という。色類はマッチングであり、逆に $E$ を $k$ 個のマッチング $M_1,\dots,M_k$ の交わらない和に分ければ、$M_i$ の辺に色 $i$ を塗って $k$-辺彩色が得られる。よって $\chi'(G)$ は、$E$ をマッチングに分けるときの個数の最小値である。
辺を頂点とし、隣接する 2 辺を隣り合わせたグラフを線グラフ $L(G)$ とすると、$G$ の辺彩色は $L(G)$ の頂点彩色と同じものであり（彩色 の記事の命題「辺彩色と線グラフの頂点彩色」）、$\chi'(G)=\chi(L(G))$ である。ここで $\chi$ は彩色数である。
辺をもつグラフ $G$ で、$\chi'(G)=\Delta(G)$ となるものを 第 1 類（class 1）、$\chi'(G)>\Delta(G)$ となるものを 第 2 類（class 2）という。ここで $\Delta(G)$ は最大次数である。
直感
学校の時間割を考える。教員と学級を頂点とし、教員 $X$ が学級 $Y$ を 1 コマ受け持つごとに $X$ と $Y$ を辺で結ぶ（同じ組を複数コマ受け持つなら平行な辺を引く）。1 コマの時間帯に、1 人の教員は 1 つの学級しか教えられず、1 つの学級は 1 人の教員からしか習えない。時間帯を色とすると、時間割はちょうど辺彩色であり、必要な時間帯の最小数が辺彩色数である（BM76 §6.3、p. 96）。最も忙しい教員や学級の受け持ちコマ数、すなわち最大次数より少ない時間帯では足りない。教員と学級の組は二部グラフになるので、実は最大次数と同じ数の時間帯で足りる（多重グラフ の記事の定理「König の辺彩色定理」）。
例
- 星 $K_{1,n}$（$n\ge1$）では、中心に $n$ 本の辺が集まるので $\chi'=n=\Delta$ である。一方、頂点の彩色数は $2$ である。辺彩色数と彩色数は別の量である。
- 長さ $n$ の閉路 $C_n$ では $\Delta=2$ である。$n$ が偶数なら 2 色を交互に塗ればよく $\chi'=2$ である。$n$ が奇数なら、2 色の色類はそれぞれ高々 $(n-1)/2$ 本の辺しか含まないので $n$ 本の辺を覆えず、3 色目に 1 本を塗れば足りて $\chi'=3$ である。
- 道 $P_n$（$n\ge2$）と、一般に辺をもつ二部グラフは第 1 類である（多重グラフ の記事の定理「König の辺彩色定理」）。完全二部グラフ $K_{m,n}$ については、辺 $x_iy_j$ に色 $i+j\bmod n$ を塗る具体的な塗り方がある（完全二部グラフ の記事の定理「完全二部グラフの辺彩色数」）。
外側の頂点 $v_0,\dots,v_4$、内側の頂点 $u_0,\dots,u_4$ をもち、辺が $v_iv_{i+1}$、$v_iu_i$、$u_iu_{i+2}$（添字は $5$ を法とする）である Petersenグラフ $P$ の辺に、次のように色を塗る。
色の表を開く
外側：$v_0v_1\mapsto1$、$v_1v_2\mapsto2$、$v_2v_3\mapsto1$、$v_3v_4\mapsto2$、$v_4v_0\mapsto3$。
外と内を結ぶ辺：$v_0u_0\mapsto2$、$v_1u_1\mapsto3$、$v_2u_2\mapsto3$、$v_3u_3\mapsto3$、$v_4u_4\mapsto1$。
内側：$u_0u_2\mapsto1$、$u_1u_3\mapsto1$、$u_2u_4\mapsto2$、$u_3u_0\mapsto4$、$u_4u_1\mapsto4$。
各頂点に集まる 3 本の色は、$v_0$ で $1,3,2$、$v_1$ で $1,2,3$、$v_2$ で $2,1,3$、$v_3$ で $1,2,3$、$v_4$ で $2,3,1$、$u_0$ で $2,1,4$、$u_1$ で $3,1,4$、$u_2$ で $3,1,2$、$u_3$ で $3,1,4$、$u_4$ で $1,2,4$ であり、どれも相異なる。
これは 4-辺彩色なので $\chi'(P)\le4$ である。3 色では塗れないこと（thm-ec-petersen）と合わせて $\chi'(P)=4$ となる。
基本的な評価
辺をもつ $n$ 頂点のグラフ $G$ について、
$$\max\Bigl\{\Delta(G),\ \frac{|E|}{\lfloor n/2\rfloor}\Bigr\}\le\chi'(G)\le2\Delta(G)-1$$
が成り立つ。
最大次数の頂点に集まる $\Delta(G)$ 本の辺は互いに隣接するので、相異なる色を要する。マッチングの辺は端点を共有しないので、マッチングは高々 $\lfloor n/2\rfloor$ 本の辺しか含まない。$\chi'(G)$ 個の色類で $|E|$ 本の辺を覆うので $|E|\le\chi'(G)\lfloor n/2\rfloor$ である。
上界：辺 $e=ab$ に隣接する辺は、$a$ に集まる他の $\deg(a)-1$ 本と $b$ に集まる他の $\deg(b)-1$ 本で、高々 $2\Delta(G)-2$ 本である。よって線グラフ $L(G)$ の最大次数は $2\Delta(G)-2$ 以下であり、彩色数 の記事の命題「彩色数の基本評価」により $\chi'(G)=\chi(L(G))\le2\Delta(G)-1$ である。$\square$
上界 $2\Delta-1$ は、辺を 1 本ずつ順に、隣接するすでに塗った辺に使われていない最小の色で塗る手順が与えるものである。実際の値はずっと小さい。
単純グラフ $G$ について $\Delta(G)\le\chi'(G)\le\Delta(G)+1$ である。
この記事では Vizing の定理は証明しない。Vizing（1964）と Gupta（1966）が独立に示し、BM76 Theorem 6.2（p. 93）に Fournier（1973）による証明がある。ループのない多重グラフでは、2 頂点を結ぶ辺の本数の最大値（多重度）を $\mu$ として $\chi'\le\Delta+\mu$ が成り立ち（BM76 §6.2、p. 95）、3 頂点の各対を $\mu$ 本ずつの辺で結んだ「太い三角形」では等号 $\chi'=3\mu=\Delta+\mu$ となる（多重グラフ の記事の例「太い三角形」）。単純グラフに限れば第 2 類は $\chi'=\Delta+1$ を意味する。
二部グラフでは $\chi'=\Delta$ で、二部グラフは第 1 類である（多重グラフ の記事の定理「König の辺彩色定理」、BM76 Theorem 6.1、p. 93）。上の時間割の問題で最大次数と同じ数の時間帯で足りるのはこのためである。最大次数が $3$ の単純グラフについては、Vizing の定理を使わずに、Brooksの定理 を線グラフに使って 4 色で足りることを示せる（Brooksの定理 の記事の系「最大次数が 3 以下のグラフの辺の塗り分け」）。
完全グラフ
完全グラフの辺彩色は、総当たり戦の日程表である。$n$ チームが総当たりで 1 試合ずつ戦い、各チームが 1 日に 1 試合しかできないとき、必要な日数の最小値が $\chi'(K_n)$ である。
$n\ge2$ とする。$n$ が偶数なら $\chi'(K_n)=n-1$、$n$ が奇数なら $\chi'(K_n)=n$ である。とくに $K_n$ は、$n$ が偶数なら第 1 類、奇数なら第 2 類である。
$n$ が奇数のとき． 頂点を $\mathbb{Z}/n\mathbb{Z}$ の元 $0,1,\dots,n-1$ とし、辺 $\{i,j\}$ に色 $i+j\bmod n$ を塗る。頂点 $i$ に集まる辺 $\{i,j\}$（$j\ne i$）の色 $i+j$ は $j$ が異なれば異なるので、これは $n$-辺彩色である。逆に、$n$ が奇数なのでマッチングは高々 $(n-1)/2$ 本の辺しか含まず、辺は $n(n-1)/2$ 本あるので、prop-ec-bounds により $\chi'(K_n)\ge\frac{n(n-1)/2}{(n-1)/2}=n$ である。
$n$ が偶数のとき． $m:=n-1$ は奇数である。頂点 $0,1,\dots,m-1$ の間の辺 $\{i,j\}$ には上と同じく色 $i+j\bmod m$ を塗る。頂点 $i$ では、色 $i+j$（$j\ne i$）は $\mathbb{Z}/m\mathbb{Z}$ の $m-1$ 個の値をとり、使われていない色はちょうど $2i\bmod m$ の 1 つである。$m$ は奇数なので $2$ は $\mathbb{Z}/m\mathbb{Z}$ で逆元をもち、$i\mapsto2i$ は全単射である。そこで残りの頂点 $\infty$ と $i$ を結ぶ辺に色 $2i\bmod m$ を塗る。頂点 $i$ では、色 $2i$ はそれまで使われていなかったので、色は相異なる。頂点 $\infty$ に集まる $m$ 本の辺の色 $2i$ は $i$ ごとに異なる。よってこれは $m$-辺彩色であり、$\chi'(K_n)\le n-1=\Delta(K_n)$ である。逆の不等式は prop-ec-bounds の $\chi'\ge\Delta$ である。$\square$
$n=6$、$m=5$ とする。頂点 $0,\dots,4,\infty$ の 5 日間の日程は、色 $s$ の辺（$s$ 日目の試合）が、$i+j\equiv s\pmod5$ の組 $\{i,j\}$ と、$2i\equiv s$ となる $i$ と $\infty$ の組からなる。たとえば $s=0$ の日は $\{1,4\}$、$\{2,3\}$、$\{0,\infty\}$、$s=1$ の日は $\{0,1\}$、$\{2,4\}$、$\{3,\infty\}$ である。
正則グラフと辺の個数
正則グラフが第 1 類であることは、辺全体を完全マッチングに分けられることと同じである。
$k\ge1$ とし、$G$ を $k$-正則グラフ とする。$\chi'(G)=k$ であることと、$G$ の辺の全体が $k$ 個の完全マッチングの交わらない和に分かれることは同値である。このとき、$k$-辺彩色の各色類は完全マッチングである。
$c$ を $k$-辺彩色とする。各頂点には $k$ 本の辺が集まり、その色は $\{1,\dots,k\}$ の相異なる $k$ 個なので、どの色もちょうど 1 回ずつ現れる。よって各色類はすべての頂点をちょうど 1 回ずつ覆うマッチング、すなわち完全マッチングである。逆に $k$ 個の完全マッチングへの分解があれば、マッチングごとに色を塗れば $k$-辺彩色になる。$\square$
$n$ 頂点のグラフ $G$ が $|E|>\Delta(G)\lfloor n/2\rfloor$ を満たせば、$G$ は第 2 類である。とくに、頂点が奇数個で辺をもつ正則グラフは第 2 類である。
prop-ec-bounds により $\chi'(G)\ge|E|/\lfloor n/2\rfloor>\Delta(G)$ である。$n$ が奇数で $G$ が $k$-正則（$k\ge1$）なら、$|E|=nk/2>k(n-1)/2=k\lfloor n/2\rfloor$ である。$\square$
奇数個の頂点の $K_n$ が第 2 類であることは、この命題からも分かる。これらは BM76 Exercise 6.2.2・6.2.3（p. 96）の内容である。
3-正則グラフ
3-正則グラフでは、3 色で辺を塗れるかどうかが問題になる。次数の和 $3n$ は辺の本数の 2 倍なので、頂点の個数 $n$ は偶数である。
$G$ を 3-正則グラフ、$c$ を $G$ の 3-辺彩色とする。頂点の集合 $S$ と色 $i$ について、端点の一方だけが $S$ に属する色 $i$ の辺の本数を $b_i$ とすると、$b_i\equiv|S|\pmod2$ である。
prop-ec-regular により、色 $i$ の色類 $M_i$ は完全マッチングであり、$S$ の各頂点はちょうど 1 本の $M_i$ の辺の端点である。$M_i$ の辺のうち両端が $S$ に属するものを $a_i$ 本とすると、それらは $S$ の頂点を $2a_i$ 個覆い、端点の一方だけが $S$ に属するものは 1 個ずつ覆う。よって $|S|=2a_i+b_i$ である。$\square$
橋(グラフ理論) をもつ 3-正則グラフは第 2 類である。
3-辺彩色 $c$ があるとして矛盾を導く。橋 $e=xy$ を除いたグラフで $x$ を含む連結成分の頂点の集合を $S$ とする。端点の一方だけが $S$ に属する辺は $e$ だけである。実際、そのような辺 $f\ne e$ があれば、$f$ は $G-e$ の辺で $S$ の頂点と $S$ の外の頂点を結び、$S$ が連結成分であることに反する。よって色 $c(e)$ について $b_{c(e)}=1$、他の 2 色について $b_i=0$ であり、偶奇が異なる。これは lem-ec-parity に反する。$\square$
たとえば、完全グラフ $K_4$ の 1 本の辺の途中に新しい頂点を置いたグラフを 2 つ用意し、次数 $2$ の 2 頂点を辺で結ぶと、10 頂点の 3-正則グラフで、結んだ辺が橋になる。このグラフの辺彩色数は $4$ である（thm-ec-vizing により $4$ 以下）。同じ考え方の 3-正則グラフで完全マッチングをもたないものもある（正則グラフ の記事の例「反例：完全マッチングをもたない立方グラフ」）。
橋がなくても 3 色で塗れない 3-正則グラフがある。その代表が Petersen グラフである。
ex-ec-petersen-four の Petersen グラフ $P$ について $\chi'(P)=4$ である。
ex-ec-petersen-four により $\chi'(P)\le4$ である。3-辺彩色 $c$ があるとして矛盾を導く。$P$ は 3-正則なので、各頂点には 3 色がちょうど 1 回ずつ現れる。
外側の閉路 $v_0v_1v_2v_3v_4$ の 5 本の辺を考える。各色類はこの長さ $5$ の閉路の中でマッチングなので高々 $2$ 本であり、5 本を 3 色で覆うので、2 色が 2 本ずつ、残りの 1 色（$\alpha$ とする）が 1 本である。$\alpha$ の辺を $v_jv_{j+1}$ とする。頂点 $v_i$ で辺 $v_iu_i$ の色は、$v_i$ の外側の 2 辺に現れない色である。外側に 2 本ある色の辺は 4 頂点を覆うので、その色が $v_iu_i$ に現れる $i$ は 1 つだけである。色 $\alpha$ の辺は $v_j,v_{j+1}$ だけを覆うので、$v_iu_i$ の色が $\alpha$ となるのは $i=j+2,j+3,j+4$ の 3 つである。よって、外と内を結ぶ 5 本の辺のうち、色 $\alpha$ はちょうど 3 本で、それは $u_{j+2},u_{j+3},u_{j+4}$ に集まる辺であり、他の 2 色は 1 本ずつである。
内側の辺 $u_iu_{i+2}$ も長さ $5$ の閉路 $u_0u_2u_4u_1u_3$ をなすので、同じ議論が使える。内側に 1 本だけ現れる色を $\beta$ とすると、外と内を結ぶ辺のうち色 $\beta$ のものは 3 本で、それは内側の $\beta$ の辺の端点でない 3 頂点に集まる。外と内を結ぶ辺で 3 本現れる色は $\alpha$ だけなので $\beta=\alpha$ であり、内側の $\alpha$ の辺の端点は、$u_{j+2},u_{j+3},u_{j+4}$ 以外の 2 頂点 $u_j,u_{j+1}$ である。しかし内側の辺は添字の差が $\pm2$ の 2 頂点を結ぶので、$u_j$ と $u_{j+1}$ は辺で結ばれていない。これは矛盾である。$\square$
Hamilton 閉路をもつ 3-正則グラフは 3 色で塗れる。頂点の個数が偶数なので Hamilton 閉路は偶数の長さで、その辺に 2 色を交互に塗ると、各頂点に残る 1 本の辺どうしは端点を共有しないので、3 色目で塗れるからである（BM76 Exercise 9.6.4、p. 159）。したがって thm-ec-petersen から、Petersen グラフが Hamilton 閉路をもたないことも従う（別の証明が Hamilton閉路 の記事の命題「Petersenグラフが Hamilton閉路をもたないこと」にある）。
四色定理 は、「連結で橋をもたない単純な 3-正則の平面グラフはすべて 3 色で辺を塗れる」という主張と同値である（BM76 Theorem 9.12、p. 158）。この同値性は Tait（1880）が最初に指摘した（同書 p. 159）。この記事ではこの同値性は証明しない。Petersen グラフは平面グラフではない（平面グラフ の記事の例「Petersenグラフは平面グラフでない」）ので、thm-ec-petersen はこの主張の反例にはならない。
反例の表
| 外す条件 | 反例 | 成り立たなくなること |
|---|---|---|
| 二部グラフ（König の辺彩色定理） | 三角形 $K_3$ | $\chi'=3>2=\Delta$ |
| 単純グラフ（Vizing の定理） | 3 頂点の各対を $\mu\ge2$ 本の辺で結んだ太い三角形 | $\chi'=3\mu>2\mu+1=\Delta+1$ |
| 頂点の個数が偶数（thm-ec-complete の $\chi'(K_n)=n-1$） | $K_3$、$K_5$ | $\chi'(K_n)=n=\Delta+1$ |
| 橋をもつ（cor-ec-bridge の逆「橋がなければ第 1 類」） | Petersen グラフ | 橋のない 3-正則グラフだが $\chi'=4$ |
| 塗る順番を選ぶ（貪欲な塗り方） | 道 $P_5$ の辺 $e_1,e_2,e_3,e_4$ を $e_1,e_4,e_2,e_3$ の順に塗る | $e_1,e_4$ が色 $1$、$e_2$ が色 $2$、$e_3$ は隣の $e_2,e_4$ が色 $2,1$ なので色 $3$ となり、$\chi'(P_5)=2$ より多い色を使う |
2 行目の太い三角形はどの 2 辺も端点を共有するので、$3\mu$ 本の辺はすべて異なる色を要し、各頂点の次数は $2\mu$ である（多重グラフ の記事の例「太い三角形」）。4 行目の Petersen グラフに橋がないことは、どの辺も長さ $5$ の閉路に含まれることから分かる（閉路に含まれる辺は橋でない。閉路 の記事の定理「閉路に含まれる辺と橋」）。外側の辺は外側の閉路に、内側の辺は内側の閉路に含まれ、辺 $v_0u_0$ は閉路 $v_0u_0u_2v_2v_1v_0$ に含まれ、他の外と内を結ぶ辺も添字をずらした閉路に含まれる。
補足
- 辺彩色数と彩色数：$\chi'(G)=\chi(L(G))$ なので、辺彩色は線グラフという特別なグラフの頂点彩色である。一般のグラフの彩色数は最大次数よりずっと小さいこともある（Brooksの定理）が、辺彩色数は最大次数とほとんど同じ値しかとらない。
- 多重グラフ：ループのない多重グラフでも辺彩色と辺彩色数は同じ定義で考えられ、平行な辺は異なる色を要する。二部の多重グラフは第 1 類である（多重グラフ の記事の定理「König の辺彩色定理」）。
- 時間割と総当たり：BM76 §6.3（pp. 96–）は、教員と学級の時間割を二部の多重グラフの辺彩色として扱う。総当たり戦の日程は thm-ec-complete の構成で作れる。
- 文献：辺彩色の基本事項は BM76 第 6 章（§6.1 p. 91 から）にある。Petersen グラフの辺彩色数が $4$ であることは同書 Exercise 6.1.2（p. 93）、$\chi'(K_{2n-1})=\chi'(K_{2n})=2n-1$ は Exercise 6.2.1（p. 96）である。
関連項目
- 前提: 彩色, マッチング(グラフ理論), 次数(グラフ), 正則グラフ
- 比較: 彩色数, 線グラフ
- 直後に読む: Vizingの定理, 多重グラフ, Brooksの定理
- 発展: 四色定理, Petersenグラフ, Hamilton閉路
参考文献
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
