📂グラフ理論

グラフ彩色とブルックスの定理

定義

ループがないグラフ$G$に対して、次のような関数$f : V(G) \to [k]$を$G$の**$k$-カラーリングという。 $$ u \sim v \implies f(u) \ne f(v) $$ グラフ$G$が$k$-カラーリングを持っていれば、$k$-塗り分け可能ともいう。もし$k$-塗り分け可能であって$(k-1)$-塗り分け不可能なら、その$k$を$G$のクロマチック数**^{chromatic number}と呼び、$\chi(G) = k$と表示される。クロマチック数が$k$のグラフを**$k$-クロマチックグラフ**という。

---

• ループとは、頂点$u$が自分自身と隣接しているエッジのこと。
• $[k] = \left\{ 1, \cdots , k \right\}$は$1$から$k$までの自然数を集めた集合を意味している。ここで自然数に大きな意味はなく、$k$個の異なる要素さえあれば抽象的にカラーリングの値域になり得る。例えば$[3] = \left\{ \text{red}, \text{blue}, \text{black} \right\}$でも良いが、$\left\{ 1,2,3 \right\}$と本質的に違うわけではないため自然数を使用する。

説明

グラフのカラーリングをわかりやすく言うと、隣接する頂点同士を異なる色で塗り分けることをいう。そのような関数は無数に存在するため、自然と私たちの関心事になるのは最小限の塗り分けとなるだろうから、塗り分け可能という表現はあまり使われない。

グラフのクロマチック数を判定する問題は組み合わせ論で常に注目を浴びており、中でも有名だったのがかつて難問として悪名高かった4色問題である。一般に、こうした問題はNP問題に属し、今も革新的なアルゴリズムや定理の証明を待っている。

任意のグラフに対して最も簡単に思いつく塗り分けは、ただ$n$個の頂点を$n$個の異なる色で塗ることである。このような塗り分けをグリーディーカラーリングというが、当然ながら最も愚直な方法である。グラフの性質に応じて、以下のように様々な定理が知られている。グラフカラーリングに触れるとき、最初に接することになり、また最も有名な定理の一つがブルックスの定理である。

定理 ¹

• $$ \chi(K_{n}) = n \\ \chi(G) = 1 $$
• [2]: $G$がヌルグラフでなく二部グラフであることと$\chi(G) = 2$は等価である。
• [3]: シンプルグラフ$G$の最大次数を$\Delta (G)$とすると $$ \chi(G) \le \Delta (G) +1 $$
• $$ \chi(G) \le \sqrt{2m+1/4}+1/2 $$
• [5] ブルックスの定理：シンプル連結グラフ$G$が完全グラフでなくて、最大次数が$\Delta (G) \ge 3$なら、$G$は$\chi(G) \le \Delta (G)$