五色定理

五色定理は、世界各国の政治地図など、地域に分割された平面が与えられた場合、隣接する 2 つの地域が同じ色にならないように、最大​​ 5 色を使用して地域を色分けできるというグラフ理論の結果です。

五色定理は、より強い四色定理から導かれるが、証明するのはかなり簡単である。これは、1879年にアルフレッド・ケンプが四色定理を証明しようとして失敗した試みに基づいていた。パーシー・ジョン・ヒーウッドは11年後に誤りを発見し、ケンプの研究に基づいて五色定理を証明した。

まず、単純な平面グラフを 与えられたマップに関連付けます。つまり、マップの各領域に頂点を配置し、対応する領域が共通の境界を共有している場合に限り、2 つの頂点を辺で接続します。次に、この問題はグラフの色付け問題に変換されます。つまり、どの辺の端点も同じ色にならないように、グラフの頂点をペイントする必要があります。 ${\displaystyle G}$

は単純な平面グラフ、つまり、交差する辺なしに平面に埋め込むことができ、2 つの頂点が複数の辺を共有せず、ループもないため、(平面のオイラー特性を使用して) 最大 5 つの辺によって共有される頂点を持つ必要があることが示されます。(注: これは、証明で 5 色条件が使用される唯一の場所です。この手法を 4 色定理の証明に使用すると、このステップで失敗します。実際、二十面体グラフは5 正則かつ平面であるため、最大 4 つの辺によって共有される頂点はありません。) そのような頂点を見つけて と呼びます。 ${\displaystyle G}$${\displaystyle v}$

次に、から を削除します。この方法で得られたグラフはよりも頂点が 1 つ少ないため、帰納的に5 色のみで色付けできると仮定できます。 の 5 つの隣接頂点で 5 色すべてを使用して色付けしなかった場合、 は隣接頂点で使用されていない色で色付けできます。次に、 に循環順序で隣接していた5 つの頂点、、、、を見ます(これはG の書き方によって異なります)。したがって、、、、はそれぞれ色 1、2、3、4、5 で色付けされている と仮定できます。${\displaystyle v}$${\displaystyle G}$${\displaystyle G'}$${\displaystyle G}$${\displaystyle v}$${\displaystyle G}$${\displaystyle v_{1}}$${\displaystyle v_{2}}$${\displaystyle v_{3}}$${\displaystyle v_{4}}$${\displaystyle v_{5}}$${\displaystyle v}$${\displaystyle v_{1}}$${\displaystyle v_{2}}$${\displaystyle v_{3}}$${\displaystyle v_{4}}$${\displaystyle v_{5}}$

ここで、色 1 と 3 のみで色付けされた頂点と、それらを接続する辺で構成されるのサブグラフについて考えます。明確にするために、各辺は色 1 の頂点を色 3 の頂点に接続します (これはKempe チェーンと呼ばれます)。とが の異なる連結成分にある場合、の残りの部分の色付けに影響を与えることなく、を含む成分の 1 と 3 の色を入れ替えることができます。これにより、色 1 がタスクを完了するために解放されます。逆に、 とが の同じ連結成分にある場合、それらを結合する際に色 1 と 3 の頂点のみで構成されるパスを見つけることができます。 ${\displaystyle G_{1,3}}$${\displaystyle G'}$${\displaystyle v_{1}}$${\displaystyle v_{3}}$${\displaystyle G_{1,3}}$${\displaystyle v_{1}}$${\displaystyle G'}$${\displaystyle v}$${\displaystyle v_{1}}$${\displaystyle v_{3}}$${\displaystyle G_{1,3}}$${\displaystyle G_{1,3}}$

次に、色 2 と 4 のみで色付けされた頂点とそれらを接続する辺で構成されるのサブグラフに目を向け、前と同じ議論を適用します。すると、を含むのサブグラフで 2-4 の色付けを反転して色 2を塗るか、色 2 と色 4 の頂点のみで構成されるパスでと を接続することができます。このようなパスは、から は循環順序であるため、前に構築した 1-3 色のパスと交差します。これは、グラフの平面性と矛盾するため、明らかに不合理です。 ${\displaystyle G_{2,4}}$${\displaystyle G'}$${\displaystyle G_{2,4}}$${\displaystyle v_{2}}$${\displaystyle v}$${\displaystyle v_{2}}$${\displaystyle v_{4}}$${\displaystyle v_{1}}$${\displaystyle v_{5}}$

したがって、最初の推定に反して、実際には 5 色である可能性があります。 ${\displaystyle G}$

1978 年の Lipton と Miller に始まり、複数の著者が平面グラフの 5 色塗りの効率的なアルゴリズムを研究してきました。Lipton と Miller のアルゴリズムは 時間がかかりましたが[ ^1]、その後の研究者は にまで時間制限を短縮しました。^{[2] [3] [4] [5] [6]}以下のバージョンは、Robertson、Sanders、Seymour、および Thomas による 1996 年の論文からの抜粋で、この論文では、このアルゴリズムを4 色塗りのより遅い 時間のアルゴリズムと関連させて簡単に説明しています。^[7]ここで説明するアルゴリズムは、マルチグラフに対して動作し、1 組の頂点間に複数の辺のコピーを持つ機能に依存しています。これは、次のことを述べる We​​rnicke の定理に基づいています。${\displaystyle O(n\log n)}$${\displaystyle O(n)}$${\displaystyle O(n^{2})}$

ウェルニッケの定理: G は平面で、空でなく、2 つの辺で囲まれた面を持たず、最小次数が5 であると仮定します。この場合、G には次数 5 の頂点があり、その頂点は次数 6 以下の頂点に隣接しています。

各頂点が時計回りの平面順序で隣接する頂点の循環リンク リストを維持するグラフの表現を使用します。

概念的には、アルゴリズムは再帰的であり、グラフを頂点が 1 つ少ない小さなグラフに縮小し、そのグラフを 5 色に着色し、その着色を使用して定数時間で大きなグラフの着色を決定します。実際には、縮小されたグラフごとに明示的なグラフ表現を維持するのではなく、グラフから頂点を削除しながらスタックに追加し、最後にスタックから戻すときに着色します。次の 3 つのスタックを維持します。

• S ₄ : 次数が最大 4 であるか、次数が 5 で隣接する頂点が最大 4 個 (複数の辺があるため) である残りのすべての頂点が含まれます。
• S ₅ : 次数が 5 である残りのすべての頂点、5 つの異なる隣接頂点、および次数が最大 6 である少なくとも 1 つの隣接頂点が含まれます。
• S _d : これまでグラフから削除されたすべての頂点が、削除された順序で含まれます。

アルゴリズムは次のように動作します。

1. 最初のステップでは、すべての多重エッジを単一のエッジに縮小して、グラフをシンプルにします。次に、グラフの頂点を反復処理して、S ₄または S ₅の条件に一致する頂点を適切なスタックにプッシュします。
2. _{次に、 S 4}が空でない限り、 S _4からv をポップし、グラフからv を削除して、この時点での隣接ノードのリストとともにS _{dにプッシュします。} vの以前の隣接ノードをそれぞれチェックし、必要な条件を満たしている場合はS ₄または S ₅にプッシュします。
3. S ₄が空になると、グラフの最小次数が 5 であることがわかります。グラフが空の場合は、最後のステップ 5 に進みます。それ以外の場合は、ウェルニッケの定理により、 S ₅は空でないことがわかります。S _5からv を取り出してグラフから削除し、v ₁、v ₂、v ₃、v ₄、v _{5 を}時計回りの平面順序でvの以前の隣接ノードとします。ここで、 v _{1 は次数が最大で 6 の隣接ノードです。} v _1がv ₃に隣接しているかどうかを確認します(これは、 v ₁の次数により定数時間で実行できます)。次の 2 つのケースがあります。
   1. v _1がv ₃に隣接していない場合、これらの 2 つの頂点を 1 つの頂点にマージできます。これを行うには、両方の円形隣接リストからv を削除し、次に、 v が以前見つかったポイントで 2 つのリストを 1 つのリストに接合します。 v が各リスト内の位置への参照を保持している場合、これは定数時間で実行できます。これにより、リストが接合された 2 つのポイントで 2 つのエッジで囲まれた面が作成される可能性があり、そのような面から 1 つのエッジを削除します。これを実行した後、v _{3 を}S _{dにプッシュし、} v ₁がマージされた頂点であることをメモします。マージの影響を受ける頂点は、必要に応じてスタックに追加または削除されます。
   2. それ以外の場合、v _{2 は}v、v ₁、v ₃で囲まれた面の内側にあります。したがって、v _{2 は、この面の外側にある}v ₄に隣接できません。上記のv ₁とv ₃と同じ方法で、v ₂とv _{4 を}マージします。
4. ステップ2に進みます。
5. この時点では、 S ₄、 S ₅、およびグラフは空です。 S _dから頂点を削除します。頂点がステップ 3 で別の頂点と結合された場合、結合された頂点はすでに色付けされているので、同じ色を割り当てます。これは、元のグラフで隣接していなかった頂点のみを結合したため有効です。ステップ 2 で、最大で 4 つの隣接頂点があったために削除した場合、削除時にすべての隣接頂点はすでに色付けされているので、隣接頂点のいずれも使用していない色を単に割り当てることができます。

カイネン（1974）は、 K6（ 6頂点の完全グラフ）の非平面性とグラフマイナーに基づいて、5色定理の簡略化された証明を提供しています。この証明は、2つの辺を削除することで平面にできるグラフに一般化されます。_[ ^8]

• 四色定理

• Heawood, PJ (1890)、「地図色定理」、Quarterly Journal of Mathematics、オックスフォード、第 24 巻、pp.  332– 338