平面グラフとその彩色

グラフ $G = (V, E)$ は、頂点の有限集合 $V$ と、頂点の 2 元部分集合からなる辺の集合 $E$ の組です。この記事のグラフはすべて単純、すなわち自己ループも多重辺もないものとします。頂点 $v$ に接する辺の本数を $v$ の次数といい $\deg(v)$ と書きます。

$G$ が平面グラフであるとは、頂点を平面上の相異なる点に、辺を端点を結ぶ曲線に対応させて、辺どうしが端点以外で交わらないように描けることをいいます。そのような描き方を 1 つ固定したものを平面描画と呼びます。

写像 $c \colon V \to \{1,\ldots,k\}$ が $G$ の**$k$ 彩色であるとは、辺 $\{u,v\} \in E$ をもつどの 2 頂点についても $c(u) \neq c(v)$ が成り立つことをいいます。$k$ 彩色が存在する最小の $k$ を $G$ の彩色数** $\chi(G)$ といいます。