📂グラフ理論

グラフ理論における地図の定義

定義 ¹

1. $3$-接続された平面グラフは地図と定義された。
2. 同じエッジの間で隣接するフェイスが異なる色になるように、$k$個の色で塗ることができる地図を**$k$-フェイス着色可能地図**という。
3. 既存の$k$-着色可能グラフを**$k$-頂点着色可能グラフ**という。

---

• 平面グラフを描くとき、平面上で区別される領域をフェイスと呼ぶ。

説明

1. $3$-グラフは地図と呼ばれないケースを除外するための制約で、短くて明確だからすごくいい定義だ。以下はそれぞれ$1$個、$2$個の頂点で断絶するグラフの例で、実際の地図ではあり得ないケースだ。左のケースでは非現実的なエッジがあるため一つの赤い頂点を取り除くと断絶グラフになり、右のケースでは非現実的な頂点があるため両側の赤い頂点を取り除くと断絶グラフになる。

2. このような地図の各エリア、つまりフェイスを別の色で区別するためには、最低何色が必要だろうか？地図が複雑になるほど色は増えそうだが、隣り合うだけなら想像以上に多くの色は必要ない。例えば、以下は世界地図をたった$4$色で着色したものだ。 このような質問は$k$-フェイス着色という数学的な概念に抽象化できる。これは典型的な組合せ理論スタイルの問題で、ただの世界地図ではなく、存在できる全ての地図が$4$色で区別できるかどうかに対する質問が、まさに$4$色問題だ。

3. 頂点着色は単に地図のフェイス着色と区別するために使われる言葉だ。$4$色問題は以下のような定理を通じてグラフ理論の問題として解くことができる。

定理

$G$がシンプルで接続された平面グラフであり、$G^{ \ast }$がその幾何学的デュアルである場合、次のことが成り立つ。 $G$は$k$-頂点着色可能であり、$G^{ \ast }$は$k$-フェイス着色可能である。

証明

戦略: 本当の「証明」と言えるものではなく、デュアルグラフの概念から自然に得られる結果だ。

---

$(\Rightarrow)$

$G$はシンプルで接続されたグラフなので、$G^{ \ast }$は地図だ。もし $G$が頂点に対する$k$-着色を持っていれば、各$v \in V(G)$に対応する$G^{ \ast }$のフェイス$f^{ \ast }$に対してもまったく同じ$k$-着色を施すことができる。$G$で隣接する頂点が仮定によって異なる色で着色されていたので、$G^{ \ast }$の隣接するフェイスも異なる色で着色される。したがって、$G^{ \ast }$は$k$-フェイス着色可能である。

---

$(\Leftarrow)$

反対の証明も本質的に異なるものではない。

■