四色定理のソースを表示

[[ファイル:Four Colour Map Example svg jp.PNG|サムネイル|266x266ピクセル|4色に塗り分けられている（常にさらに外側の領域を想定することで、地図の外縁部は3色で塗り分け可能で、球面においても四色定理が成立することがわかる）]]
'''四色定理'''（よんしょくていり／ししょくていり、{{Lang-en-short|Four color theorem}}）とは、厳密ではないが日常的な直感で説明すると「平面上のいかなる地図も、隣接する領域が異なる色になるように塗り分けるには4色あれば十分だ」という定理である。

==定理の正確な定式化==
グラフ理論的に言えば、この定理はループのない[[平面グラフ]]に対して次のことを述べている。[[平面グラフ]]<math>G</math>に対して、その[[グラフ彩色|彩色数]]は<math>\chi(G) \leq 4</math>である。

四色定理の直観的な記述 - 「平面を連続した領域に分割したとき、隣接する2つの領域が同じ色を持たないように、領域は最大でも4つの色を使って着色できる」 - を正しく解釈する必要がある。

これを「地図の塗り分け」とすると、例えば[[飛地|飛び地]]を所属地と常に同じ色にしなければならない、とした場合、何色あっても足りない、といった問題などがある。例えば、簡略化した地図を考えてみると：

[[File:4CT Inadequacy Example.svg|center|200px]]

この地図では、''A''と書かれた二つの地域は同じ国に属している。もしこれらの領域に同じ色を与えたいならば、5つの色が必要になる。なぜなら、2つの''A''領域は一緒になって他の4つの領域に隣接し、それぞれの領域は他のすべての領域に隣接しているからである。なお別々の領域に同じ色を持たせることは、平面の外側にそれらをつなぐ'ハンドル'を追加することでモデル化できる。

[[File:4CT Inadequacy Explanation.svg|center|200px]]

このような構成によって、この問題は[[トーラス]]（[[種数]]1の曲面）上の地図の色付け問題と等価になる。

よってまず、日常的な直感から離れた表現で記述し直すと「境界線によって囲まれたいくつかの領域からなる平面図形があり、境界線の一部を共有する（隣り合った）領域は異なった色で塗らなければならない、としたとき、4色あれば十分である」となる。

[[グラフ理論]]でとらえると、
:「[[平面グラフ]]は4彩色可能である」
という定理になる（後述）。

なお、境界線ではなく、点のみを共有する領域は隣り合っているものとはみなされず、互いに同色で塗ってもよい（飛び地の場合と同じく、この条件なしではやはり何色あっても足りなくなる。現実の地図では稀だが、有名なものでは米国に、1点に4州が接する「[[フォー・コーナーズ (アメリカ合衆国)|フォー・コーナーズ]]」という地点がある）。また平面だけでなく、球面の場合も同様である（平面の地図に、全周囲となる領域を加え、それを反対側の1点に集めるようにして球にすればよい。逆も同様）。しかし、ドーナツや「繋がったドーナツ」のような、穴がある形状の表面については同様とはいかない（これも後述）。

証明される前は'''四色問題'''と呼ばれることもあり、1975年に証明されたのだが、未証明の期間が長かったため現在でも四色問題と呼ばれることがある。

3つの境界線が1点に集まっている場所があるため、3色必要であることはただちに明らかである。続いて、ある領域の周囲にいくつかの領域がある場合（日本地図では[[長野県]]のような場合）を考える。周囲の領域の個数が偶数であれば3色で塗り分けできるが（長野県の場合はそうなる{{efn2|新潟県・群馬県・埼玉県・山梨県・静岡県・愛知県・岐阜県・富山県 の8県。}}）、奇数個の領域で囲まれている場合は3色での塗り分けは不可能で、どうしても4色が必要である。そして、4色あればどんな場合でも塗り分け可能なのか？　ということが問題である。

前述のように、[[グラフ理論]]により「[[平面グラフ]]は4彩色可能である」という定理となる（証明もグラフ理論によってなされている）。参考例を図に示すが、まず、地図の境界線をグラフの辺、境界線が接続する点をグラフの頂点としたグラフを作る。その[[双対]]グラフにおける頂点の彩色が、元の地図の塗分けと同じ問題となる。
[[Image:Four Colour Planar Graph.svg|center|]]

また、このような領域の塗り分けが有限の色数で必ず可能となるのは平面（二次元）以下の次元までであり、三次元以上では領域の取り方次第でいくらでも色数が必要な例が作れる。

== 歴史 ==
[[Image:Map of USA with state names.svg|thumb|270px|（海や他国領土の色を除いて）4色に塗り分けられた[[アメリカ合衆国]]の州]]
1852年に法科学生の[[フランシス・ガスリー]]が数学専攻である弟の{{仮リンク|フレデリック・ガスリー|en| Frederick Guthrie}}に質問したのを発端に問題として定式化され、19世紀後半になって[[数学者]]がその話を聞いて証明を試みたが、多くの数学者の挑戦をはねのけ続けていた。

1879年、{{仮リンク|アルフレッド・ケンプ|en|Alfred Kempe}}による証明が『[[アメリカ数学ジャーナル]]』誌上で発表された。この証明は妥当と見なされていたが、1890年になって{{仮リンク|パーシー・ヒーウッド|en|Percy John Heawood}}により不備が指摘された。しかし、ケンプの証明で使われた論理に沿って、地図を塗り分けるには5色で十分であることが証明された。これは[[五色定理]]と呼ばれている。4色で十分かどうかは、[[グラフ理論]]における最も有名な未解決問題として残った。

[[1976年]]に{{仮リンク|ケネス・アッペル|en|Kenneth Appel}}と[[ヴォルフガング・ハーケン]]は、{{仮リンク|ハインリヒ・ヘーシュ|en|Heinrich Heesch}}により考案された「[[放電法]]」と呼ばれる手続きを改良し、[[コンピュータ]]を利用して約2000個の（後に1400個あまりに整理された）可約な配置からなる不可避集合を見出し、四色定理を「証明」するに至った<ref>K. Appel, W. Haken, "''Every planar map is four colorable''" (Bulletin of the American Mathematical Society Volume 82, Number 5, September 1976)</ref><ref>"''Every planar map is four colorable. Part II: Reducibility''" by K. Appel, W. Haken, and J. Koch (Illinois J. Math. Volume 21, Issue 3 (1977), 491–567.)</ref><ref>Contemporary mathematics 98 "''Every Planar Map is Four Colorable''" by Kenneth Appel and Wolfgang Haken</ref>。

これは一応は認められたが、人手による実行が（事実上）不可能なほどの複雑なプログラムの実行によるものであることから、ハードウェアやソフトウェア（コンピュータやその[[プログラム (コンピュータ)|プログラム]]）のバグの可能性などの懸念から、その確実さについて疑問視する向きもあった。たとえば、[[東京女子大]]の小西善二郎講師は、元のSystem/370は現在入手不可能だが、等価回路で元の[[アセンブリ言語|アセンブラ]]によるプログラムの欠陥がないとは言えない、としている。

しかしその後、1996年に{{仮リンク|ニール・ロバートソン|en|Neil Robertson (mathematician)}}らによりアルゴリズムやプログラムの改良が行われ、より簡易な手法（従来の放電手続きよりシンプルな放電手続きを考案し、不可避集合の数を1405個から633個に抑えた）による再証明が行われる<ref>"''A new proof of the four-colour theorem''" by Neil Robertson, Damiel P. Sanders, Paul Seymour, and Robin Thomas (Electronic Research Announcements of the American Mathematical Society Volume 2, Number 1, August 1996)</ref>など、第三者による複数の改良された証明が行われ、証明は確実視されるようになっていった。2004年には{{仮リンク|ジョルジュ・ゴンティエ|en|Georges Gonthier}}が定理証明系[[Coq]]を用いて、よりシンプルな証明を行うなど<ref>"''A computer-checked proof of the Four Colour Theorem''" by Georges Gonthier (Microsoft Research Cambridge) http://www2.tcs.ifi.lmu.de/~abel/lehre/WS07-08/CAFR/4colproof.pdf</ref>、コンピュータの応用手法の洗練により、より確かな手続きで証明が行われるなどしているため、現在では四色問題は解決していると捉えられている。<!--

四色定理は実用的には地図作製だけでなく、[[携帯電話]]の[[基地局]]配置にも応用されている。[[周波数]]の同じ[[電波]]同士で混信してしまう[[周波数分割多元接続|FDMA]]・[[時分割多元接続|TDMA]]方式の携帯電話システムでは、隣接する基地局同士に同じ周波数を割り当てないように、配慮している。

--><!--

基地局のカバーエリアは、地図上の領域や平面グラフのように任意の広がりを持つことは一般に考えられない（3色では足りず、4色が必要であること、は、概説で述べたようにこの定理以前の単純な話である）。この分野に、基地局等に関しもし有用な理論があるとするなら、[[ドロネー図]]あるいは[[ボロノイ図]]に関する理論ではないだろうか？

-->

== コンピュータによる証明 ==
四色定理の証明法は次の2段階に分けられる。
#どのような平面グラフをとってきても、その集合に属するグラフのどれか一つが部分グラフとして含まれるグラフの集合を考える。このような性質をもつグラフの集合を'''不可避集合'''という。
#不可避集合をうまく選ぶと、それに属するどのグラフも次の意味で'''可約'''にできる。すなわち、その部分グラフを含むグラフがあったとき、その部分グラフを除いたものが4色で塗り分けが可能ならば、グラフ全体も4色で塗り分けができる。
実際、もしも塗り分けに5色以上が必要な四色問題の反例となるグラフがあったとしたならば、その中で頂点の個数が最小のものを考える。すると、1.よりこのグラフは不可避集合に属する部分グラフを含む。2.により、この部分グラフを除いた、より頂点数の少ないグラフが既に四色問題の反例を与えることになる。しかし、それは最小の反例をとってきたという仮定に反する。

アッペルとハーケンはコンピュータによる実験を繰り返し、プログラムを何度も書き換えながら、可約なグラフから成る約2,000個のグラフからなる不可避集合を求めた。当時の[[メインフレーム|大型汎用コンピュータ]]であるIBM [[System/370]]{{efn2|「最高速のスーパコンピュータ」などと書かれていることがあるが、同機はいわゆる（クレイなどの）「スーパーコンピュータ」ではない。大成功を収めた1964年発表のSystem/360（360度さまざまな業務に対応できる意）に続く、1970年発表の後継機であり、1975年当時のIBMの主力機である。System/360同様System/370ファミリを形成しており、モデルによって性能に幅がある。}}を1,200時間以上使用したといわれている。

複雑に思える問題に対して簡潔にまとまった比較的短い証明（解答）を、エレガントな証明（解答）と言うことがある。四色定理に対するある種「力業による証明」は、これとは対極にあるものとして揶揄を込めて「エレファント（[[ゾウ|象]]）」な証明とも言われた。5色による塗り分けが可能であることの証明が簡潔なものであるのとは対照的である。

その後[[アルゴリズム]]は改良されたが、現在でもコンピュータを利用しないで済ませられる証明は得られていない。それどころか完全に自然言語を離れて、プログラムにバグがないことも含めた四色定理の証明全体をコンピュータ上の証明検証系システム（ソフトウェア）[[Coq]]によってチェックさせた仕事がある。またコンピュータを使うこと以上に、証明の構成法自体が四色定理の解決のために特化していて、他の問題との関係性に乏しいことも数学者の間で人気のない理由になっている。四色問題は有名だが解決しても[[ABC予想]]みたいに数学全体に大きな影響を与える問題ではないからである。

==証明のアイディアの概要==
{{No footnotes|section|date=October 2023}}
以下の議論は''Every Planar Map is Four Colorable'' {{Harv|Appel|Haken|1989}}の序論に基づく要約である。欠点はあるが、ケンペの4色定理の最初の証明とされるものは、後に4色定理の証明に使われる基本的なツールの一部を提供した。ここでの説明は、上記の現代グラフ理論の定式化の観点から言い直したものである。

ケンペの議論は次のようなものである。まず，グラフで区切られた平面領域が''[[三角分割]]されていない場合，つまり，境界にちょうど3つの辺がない場合，境界のない外側の領域も含めてすべての領域を三角形にするために，新しい頂点を導入することなく辺を追加することができる．この[[平面グラフ|三角化グラフ]]が4色以下で着色可能であれば，辺を削除しても同じ着色法が成り立つので，元のグラフも同様である．したがって，三角形化されたグラフの4色定理を証明するには，すべての平面グラフについて証明すれば十分であり，一般性を損なうことなくグラフが三角形化されていると仮定する．

頂点、辺、領域（面）の数を ''v'', ''e'', ''f'' とする。各領域は三角形であり、各辺は2つの領域で共有されるので、2''e''=3''f''となる。これは[[オイラー標数|オイラーの多面体定理]]''v''- ''e'' + ''f'' = 2 を使えば、6''v''- 2''e'' = 12.さて、頂点の''次数''とは、その頂点に接する辺の数である。v_nを次数''n''の頂点の数、''D''を任意の頂点の最大次数とする、
:<math>6v - 2e = 6\sum_{i=1}^D v_i - \sum_{i=1}^D iv_i = \sum_{i=1}^D (6 - i)v_i = 12.</math>.
しかし、12 > 0であり、すべての''i''≥ 6に対して6 - ''i'' ≤ 0なので、これは次数5以下の頂点が少なくとも1つあることを示している。

もし5色を必要とするグラフがあるとすれば、そのようなグラフは''最小''であり、どの頂点を取り除いても4色になる。このグラフを''G''と呼ぶ。もし''d''(''v'') ≤ 3 ならば，''G''から''v''を取り除き，小さいグラフを4色化した後，''v''を再び加え，隣と異なる色を選んで4色化を拡張することができるからである．

[[File:Kempe Chain.svg|thumb|A graph containing a Kempe chain consisting of alternating blue and red vertices]]
先ほどと同様に、頂点''v''を取り除き、残った頂点を4色に着色する。もし''v''の4つの隣がすべて異なる色、例えば時計回りの順序で赤、緑、青、黄であれば、赤と青の隣を結ぶ赤と青の頂点の交互のパスを探す。このような経路は[[:en:Kempe chain|ケンプ鎖]]と呼ばれる。赤と青の隣同士を結ぶケンペ鎖があるかもしれないし，緑と黄の隣同士を結ぶケンペ鎖があるかもしれない．連鎖していないのは赤と青の隣同士だとする。赤と青の交互のパスで赤の隣の頂点に接続されているすべての頂点を探索し、これらのすべての頂点で赤と青の色を逆にする。その結果、やはり4色使いになり、''v''を戻して赤に着色することができる。

これで残るのは次数5の頂点が''G''にある場合だけであるが、ケンペの議論にはこの場合の欠陥があった。HeawoodはKempeの間違いに気付くと同時に、5色しか必要でないことを証明することで満足するのであれば、（最小反例が6色を必要とすることだけを変えて）上記の議論を実行し、次数5の状況でKempeの鎖を使って[[五色定理]]を証明することができることに気付いた。

いずれにせよ、この次数5の頂点のケースを扱うには、頂点を取り除くよりも複雑な概念を必要とする。むしろ、（Gの）各頂点の次数が指定された''G''の連結部分グラフである''構成''を考えることに議論の形式が一般化される。例えば、次数4の頂点の状況で説明されるケースは、''G''において次数4であるとラベル付けされた1つの頂点からなる構成である。上記と同様に、構成を削除して残りのグラフを4色化した場合、構成を再び追加したときに4色化も拡張できるように色付けを修正できることを示せば十分である。これが可能な構成を''還元可能な構成''と呼ぶ．ある構成の集合のうち少なくとも1つがGのどこかに必ず出現する場合、その集合を''不可避な構成''と呼ぶ。上の議論は、まず5つの構成（次数1の頂点、次数2の頂点、...、次数5の頂点）からなる不可避的な集合を与え、最初の4つが還元可能であることを示した。

G''は三角形であり、構成中の各頂点の次数は既知であり、構成内部の辺はすべて既知であるため、与えられた構成に隣接する''G''の頂点の数は決まっており、それらはサイクルで結ばれる。これらの頂点は配置の''環''を形成する。環に''k''個の頂点を持つ配置は''k''環構成であり、環を持つ配置は''環構成''と呼ばれる。上記の単純な場合と同様に、リングのすべての異なる4つのカラーリングを列挙することができる。構成のカラーリングに変更することなく拡張できるカラーリングは、''最初は良い''と呼ばれる。例えば、3つ以下の近傍を持つ上記の単一頂点の配置は、最初は良い配置であった。一般に、リングのカラーリングを良いものに変えるためには、上の4つの近傍がある場合のように、周囲のグラフを系統的に再カラーリングする必要がある。リングの4つのカラーリングの数が多いので、これはコンピュータの支援を必要とする主要なステップである。

最後に、この手順で漸化できる構成の不可避集合を特定することが残る。このような集合を発見するために使われる主要な方法は、[[放電法]]である。放電法の根底にある直感的な考え方は、平面グラフを電気的なネットワークとして考えることである。最初に正負の「電荷」が頂点に分配され、合計が正になるようにする。

上の式を思い出してほしい：

:<math>\sum_{i=1}^D (6 - i)v_i = 12.</math>

各頂点には6-deg(''v'')の初期電荷が割り当てられる。次に、ある頂点から隣接する頂点へ、規則に従って電荷を系統的に再分配することで電荷を「流す」（''discharging procedure''）。電荷は保存されるので、一部の頂点はまだ正の電荷を持っている。規則によって正電荷を持つ頂点の配置の可能性が制限されるので、そのような配置の可能性をすべて列挙すると、避けられない集合が得られる。

やむを得ない集合の中に還元可能でないものがある限り、（他の配置を導入しながら）それを取り除くように放電の手順を修正する。アペルとハーケンの最終的な排出手順は非常に複雑で、結果として得られる不可避的な構成集合の説明と合わせて400ページのボリュームを満たしたが、生成された構成が還元可能であることは機械的に確認することができた。不可避的コンフィギュレーションを記述した本そのものの検証は、数年にわたる査読によって行われた。

ここでは説明しないが、証明を完成させるために必要な技術的な詳細は、''[[はめ込み]] 可約性'''である。

=== 一般化 ===
一般に種数 ''g'' ≥ 0 の閉曲面（わかりやすく言えば、穴が ''g'' 個あるドーナツ）を塗り分けるのに最低限必要な色の数は、[[1890年]]にヒーウッドによって
:<math>\left\lfloor \frac{7+\sqrt{1+ 48g}}{2} \right\rfloor</math>（<math>\lfloor \cdot \rfloor</math>は[[床関数|フロア関数]]）
と予想された。この予測が ''g'' ≥ 1 に対して正しいことは、リンゲルとヤングスにより[[1968年]]に証明された<ref>{{MathWorld|title=Map Coloring|urlname=MapColoring}}</ref>。この式に形式的に平面の場合である g = 0 を代入すれば、4 となる（ただしこれをもって四色問題の証明とすることはできない）。

[[トーラス]]（円環、いわゆるドーナツの形、g=1の場合）上のグラフは、7色で彩色可能である。

[[Image:Torus with seven colours.svg|300px]]
[[Image:Projection color torus.png|400px]]

== 3彩色問題 ==
「与えられた地図Gに対し、Gを3色で塗り分けできるかどうかを決定せよ」という問題を'''3彩色問題'''という。四色問題のときと同じく隣り合う土地を同じ色で塗ってはならない。

3彩色問題は[[NP完全問題]]の一つであることが知られている。

== 四色問題とジョーク ==
解決される少し前の1975年に一つのハプニングがあった。[[数学パズル]]（[[:en:Recreational mathematics]]）で有名な[[マーティン・ガードナー]]が『[[サイエンティフィック・アメリカン]]』の連載コラム「Mathematical Games」において、これが四色問題の反例であるという（五色が必要だと主張する）境界の図を載せたのである<ref name="Gardner1977">{{harvtxt|ガードナー|一松|1977}}</ref><ref>{{Harvtxt|高木|1976|loc=XIV 最近の話題/パズルの最前線}}によると、日本版『サイエンス』誌6月号に掲載、と見える。</ref><ref name="一松1978pp197-204">{{Harvtxt|一松|1978|pp=197–204}}</ref>。

「なぜか世間の注意をひかなかった6つの衝撃の発見」と題する'''4月号の'''この記事は、実のところ[[エイプリルフール]]の冗談であり、他の内容もやはりラマヌジャンの定数（[[ほとんど整数#ラマヌジャンの定数]]を参照）など、一見びっくりする数学ジョークというものであった。そして「四色問題の反例」は、実はマクレガーによる[[数学パズル]]問題で、四色での塗り分けは一見不可能に見えるが、実際に塗り分けを試みればあまり難航することもなく解ける（かもしれない{{efn2|ある程度は、解く者の試行錯誤が要求され、運の要素もある。}}）というものである。そのため、塗り分けができたぞという手紙が千通以上も寄せられることになったという<ref name="一松1978pp197-204" /><ref>{{MathWorld|title=McGregor Map|urlname=McGregorMap}} このページでその問題が見られるが、解答（ネタバレ、spoiler）もすぐ隣にあるので、パズルとして楽しみたい場合は他を探すこと。</ref>。

== 脚注 ==
=== 注釈 ===
{{notelist2}}
=== 出典 ===
{{reflist|2}}

== 参考文献 ==
*{{Cite journal|和書|author1=アッペル|author2=ハーケン|author3=[[島内剛一]] 訳|year=1977|month=12|title=4色問題の解決|journal=サイエンス|issue=1977年12月号|pages=18-29|publisher=日経サイエンス|ref={{harvid|アッペル|ハーケン|1977}}}}
*{{Citation|last1=Wilson|first1=Robin|author1-link=ロビン・ウィルソン|last2=Stewart|first2=Ian|author2-link=イアン・スチュワート|date=2013-11-10|title=Four Colors Suffice: How the Map Problem Was Solved|publisher=Princeton University Press|edition=Revised Color|series=Princeton Science Library|isbn=978-0-691-15822-8|url=http://press.princeton.edu/titles/10116.html}} - 改訂多色版。イアン・スチュワートによる前書を追加。
**{{Cite book|和書|first=ロビン|last=ウィルソン|author=ロビン・ウィルソン|title=四色問題|others=[[茂木健一郎]] 訳|publisher=新潮社|date=2004-11-30|isbn=978-4-10-545201-8|ref={{Harvid|ウィルソン|2004}}}}
**{{Cite book|和書|first=ロビン|last=ウィルソン|author=ロビン・ウィルソン|title=四色問題|others=茂木健一郎 訳|series=新潮文庫 Science＆History Collection|publisher=新潮社|date=2013-12-01|isbn=978-4-10-218461-5|url=https://www.shinchosha.co.jp/book/218461/|ref={{Harvid|ウィルソン|2013}}}} - 原著初版の翻訳。
*{{Cite journal|和書|first=マーティン|last=ガードナー|author-link=マーティン・ガードナー|others=[[一松信]] 訳|year=1975|month=6|title=数学ゲーム|journal=サイエンス|issue=1975年6月号|publisher=日経サイエンス|ref={{harvid|ガードナー|一松|1977}}}}
*{{Cite book|和書|first=マーティン|last=ガードナー|author=マーティン・ガードナー|others=[[岩沢宏和]]・[[上原隆平]] 監訳|date=2016-04-20|title=ガードナーの新・数学娯楽 球を詰め込む・4色定理・差分法|publisher=日本評論社|pages=162-180|isbn=978-4-535-60423-0|ref={{harvid|ガードナー|岩沢|上原|2016}}}}
*{{Cite journal|和書|author=島内剛一|date=1977-02～09|title=四色問題|journal=数学セミナー|issue=1977年2月～9月号|publisher=日本評論社|ref={{harvid|島内|1977}}}}
*{{Cite book|和書|author=高木茂男|authorlink=高木茂男|year=1976|title=数学遊園地 数のもつ不思議さを楽しもう|publisher=講談社|series=ブルーバックス B-291|isbn=978-4-06-117891-5|ref={{Harvid|高木|1976}}}}
*{{Cite book|和書|author=一松信|authorlink=一松信|title=四色問題 その誕生から解決まで|publisher=講談社|series=ブルーバックス B-351|date=1978-04-25|isbn=4-06-117951-9|ref={{Harvid|一松|1978}}}}
**{{Cite book|和書|author=一松信|date=2016-05-29|title=四色問題 どう解かれ何をもたらしたのか|series=ブルーバックス B-1969|publisher=講談社|isbn=978-4-06-257969-8|url=https://bookclub.kodansha.co.jp/product?item=0000194930|ref={{Harvid|一松|2016}}}}
*{{Cite journal|和書|author=[[広瀬健]]|date=1977-07～10|title=四色問題と電子計算機|journal=bit|issue=1977年7月～10月号|publisher=共立出版|ref={{harvid|広瀬|1977}}}}

== 関連項目 ==
{{Commonscat|Four-color theorem}}
<!--項目の50音順-->
*[[グラフ彩色]]
*[[グラフ理論]]
*[[五色定理]]
*[[トーラス]]

== 外部リンク ==
*{{Kotobank|四色問題}}
*{{高校数学の美しい物語|1187|四色定理の紹介と五色定理の証明}}
*[http://www.justinmullins.com/four_colour_theorem.htm THE FOUR COLOUR THEOREM] - Robertsonらによる実際の633個の可約な不可避配置集合を見ることができる。[[双対グラフ]]表記のため、国が頂点、国境が枝で表される。最初の配置は[[バーコフのダイヤモンド]]であり、黒丸が5枝点を表す。以下、無印が6枝点、白丸が7枝点、四角が8枝点、三角が9枝点、五角形が10枝点で、最後の無印のみが11枝点となっている。
*[https://thomas.math.gatech.edu/FC/fourcolor.html 改良されたアルゴリズム] {{en icon}}
*{{Mathworld|title=Four-Color Theorem|urlname=Four-ColorTheorem}} -（四色定理）
*{{Mathworld|title=Map Coloring|urlname=MapColoring}} -（地図の塗り分け）
*{{Mathworld|title=Torus Coloring|urlname=TorusColoring}} -（トーラスの塗り分け）

{{DEFAULTSORT:よんしよくていり}}
[[Category:グラフ理論の定理]]
[[Category:数学に関する記事]]
[[Category:地図学]]