四色問題

質問

現在、四色問題に興味を持っています。
実際にこれが人間の頭で解けるような問題ではないことは承知済みです。何か関連性のある問題で(ex.五色問題など・・これの証明もなかなか理解できないのですが・・・）分かりやすい問題・定理の証明などございませんでしょうか？自分にはまだグラフ理論などの知識は全くありません。高校生に説明しても何とか分かる程度の問題だとありがたいです。

回答No.1

PRFRD · ベストアンサー

安直ですが，６色定理（平面的グラフは６彩色可能）はどうでしょう．
５色定理と比べると遥かに簡単に証明できますし，
証明の雰囲気は，５色定理に近いものがあります．
（検索すると，それっぽいものが何個か見つかります）

また，５色定理よりも難しい問題になりますが，
「平面ではない曲面に埋め込めるグラフ」に対する彩色定理も面白いです．
代表的なのは「穴が g 個空いた曲面」における彩色定理です．
これは，
　穴が無い曲面（球）
　穴が１個ある曲面（トーラス：ドーナツの表面）
　…
みたいに，穴が g 個ある曲面（種数が g である，と言います）を考え，
そこに交差なく描けるグラフというものを考えてやると，
平面の５色定理と同じ方針で「5 + 2g 彩色可能」が示せます．

また，よりマニアックなネタとしては「クラインの壷」に対する彩色定理：
　６彩色可能かつ，本当に６色必要なグラフは有限個のみ
なんというのもあったります（これは最近でも研究されているネタです）．

お礼

ありがとうございました。大変興味深かったです。

回答No.2

sinisorsa

ブルーバックスに一松信先生の「四色問題」があります。
その誕生から解決までとサブタイトルがついています。
大変参考になると思います。

お礼

ありがとうございました。