彩色

同義語：グラフ彩色graph coloring

概要

彩色（coloring）とは、グラフの頂点または辺へ色を割り当て、隣接する二頂点、または共通の端点を持つ二辺が同じ色にならないようにすることである。頂点彩色と辺彩色が基本で、色の名前ではなく使用可能な色数が本質となる。地図の塗り分け、時間割、周波数や資源の割当を、互いに衝突する対象へ異なるラベルを与える問題として統一的に表せる。辺彩色は線グラフの頂点彩色と同値である。

$$\newcommand{C}[0]{\mathbb{C}} \newcommand{N}[0]{\mathbb{N}} \newcommand{Q}[0]{\mathbb{Q}} \newcommand{R}[0]{\mathbb{R}} \newcommand{Z}[0]{\mathbb{Z}} $$

前提知識: グラフ, 無向グラフ

概要

グラフの彩色は、「互いに隣接する対象へ同じ色を割り当てない」という制約を写像として表す方法である。頂点を塗り分ける頂点彩色と、共通の端点を持つ辺を塗り分ける辺彩色が基本であり、地図の塗り分け、時間割、周波数割当などを同じ枠組みで扱える。
本記事では、頂点彩色と辺彩色に共通する親概念を扱う。使用する色の最小個数である彩色数・辺彩色数の詳論は、それぞれ頂点彩色と辺彩色に委ねる。

定義

本記事では、特に断らない限り、ループも平行辺も持たない有限無向グラフ $G=(V,E)$ を扱う。$S$ は空でない色の集合とする。

頂点彩色

$G$ の $S$-頂点彩色（$S$-vertex coloring）とは、写像
$$ c\colon V\to S $$
であって、辺で結ばれた任意の二頂点 $x,y$ に対して $c(x)\ne c(y)$ を満たすものをいう。

辺彩色

$G$ の $S$-辺彩色（$S$-edge coloring）とは、写像
$$ c\colon E\to S $$
であって、共通の端点を持つ相異なる任意の二辺 $e,f$ に対して $c(e)\ne c(f)$ を満たすものをいう。

色の名前と色数

$S$-頂点彩色や $S$-辺彩色が存在するかどうかは、色の名前ではなく $|S|$ だけに依存する。有限の $S$ については $S=\{1,\ldots,k\}$ としてよく、このとき $k$-頂点彩色、$k$-辺彩色という。
頂点彩色が存在する最小の $k$ を 彩色数 $\chi(G)$、辺彩色が存在する最小の $k$ を 辺彩色数 $\chi'(G)$ という。標準的な定義と基本事項は Die17 第5章を参照。

直感

色は絵具である必要はなく、互いに衝突する対象を区別するラベルである。頂点彩色では頂点が対象、辺が衝突関係を表す。例えば同時刻に置けない授業を頂点とし、衝突する二授業を辺で結べば、色を時間帯とする頂点彩色が時間割になる。
辺彩色では辺そのものが対象で、同じ頂点に接続する辺どうしを区別する。通信網の辺を通信路とみなせば、同じ中継点を同時に使えない通信へ異なる時間帯を割り当てるモデルになる。

例

色が十分多い場合

$n=|V|$ とする。$|S|\ge n$ なら、各頂点へ相異なる色を割り当てる単射 $c\colon V\to S$ は頂点彩色である。同様に $|S|\ge |E|$ なら、各辺へ相異なる色を割り当てることで辺彩色が得られる。

二部グラフの2-頂点彩色

二部グラフ $G=(V_1\mathbin{\dot\cup}V_2,E)$ では、一方の部集合 $V_1$ の全頂点を色1、他方の部集合 $V_2$ の全頂点を色2で塗れば2-頂点彩色になる。各辺の両端は異なる部集合に属するからである。

完全グラフの頂点彩色

$n$ 頂点の完全グラフ $K_n$ では、どの二頂点も隣接する。従って頂点彩色は全頂点へ相異なる色を割り当てなければならず、$S$-頂点彩色が存在するための必要十分条件は $|S|\ge n$ である。

反例：奇閉路の2-頂点彩色

偶閉路 $C_{2r}$ は、閉路に沿って2色を交互に割り当てれば2-頂点彩色できる。一方、奇閉路 $C_{2r+1}$ を2色で塗ろうとすると、ある頂点から閉路に沿って色を交互に割り当てたとき、最後の頂点は最初の頂点と同じ色になる。この二頂点は辺で結ばれているため、頂点彩色の条件が破れる。従って奇閉路は2-頂点彩色を持たない。

反例：ループを許す場合

頂点 $v$ にループがあるグラフでは、頂点彩色の条件が $c(v)\ne c(v)$ を要求してしまうため、どの色集合を用いても頂点彩色は存在しない。本記事がループを持たないグラフを扱うのは、この退化を除くためである。

性質

十分多い色による彩色

$G=(V,E)$ を有限グラフとする。$|S|\ge |V|$ なら $G$ は $S$-頂点彩色を持ち、$|S|\ge |E|$ なら $G$ は $S$-辺彩色を持つ。

$|S|\ge |V|$ のとき単射 $c\colon V\to S$ を取る。相異なる頂点 $x,y$ について $c(x)\ne c(y)$ だから、特に隣接する二頂点についてこの不等式が成り立つ。従って $c$ は $S$-頂点彩色である。
$|S|\ge |E|$ の場合も、単射 $c\colon E\to S$ を取れば相異なる二辺は異なる色を持つので、特に共通の端点を持つ二辺は異なる色を持つ。従って $c$ は $S$-辺彩色である。

色集合の単射による彩色の移送

$c\colon V\to S$ を $S$-頂点彩色、$i\colon S\to T$ を単射とすると、合成 $i\circ c\colon V\to T$ は $T$-頂点彩色である。辺彩色についても同じことが成り立つ。

隣接する頂点 $x,y$ に対して $c(x)\ne c(y)$ である。$i$ は単射なので $i(c(x))\ne i(c(y))$ となり、$i\circ c$ は頂点彩色である。辺彩色の場合は、共通の端点を持つ二辺に同じ議論を適用すればよい。

辺彩色と線グラフの頂点彩色

$G$ の線グラフを $L(G)$ とする。$G$ の $S$-辺彩色と $L(G)$ の $S$-頂点彩色は、同じ写像 $c\colon E\to S$ によって一対一に対応する。

$L(G)$ の頂点集合は $E$ であり、二頂点 $e,f\in E$ が $L(G)$ で隣接することと、二辺 $e,f$ が $G$ で共通の端点を持つことは同値である。従って写像 $c\colon E\to S$ が $G$ の隣接する二辺へ異なる色を割り当てる条件は、それが $L(G)$ の隣接する二頂点へ異なる色を割り当てる条件と同じである。

分野間の接続

  • 地図の塗り分け: 地図の領域を頂点、境界線を共有する領域の組を辺とする平面グラフの頂点彩色として表される。四色定理はこの模型で4色あれば十分であることを述べる。
  • スケジューリング: 同時実行できない仕事を辺で結び、色を時間帯とすれば頂点彩色になる。
  • 資源割当: 同じ資源を同時に使えない対象を隣接させることで、彩色は衝突を避ける割当問題になる。
  • 線グラフ: 辺彩色を頂点彩色へ変換し、二つの理論を結ぶ。

関連項目

参考文献

Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する

Mathpediaを支援する
彩色