書記が数学やるだけ#631 グラフ彩色

平面グラフをいくつかの色に塗り分ける問題を考える。

問題

説明

平面グラフの点あるいは辺を色で塗り分けていく。中でも四色定理は有名だろう，
フランシス・ガスリーの主張に始まり，1976年にケネス・アッペルとヴォルフガング・ハーケンによりコンピュータを用いた証明がなされた。しかし，いまだに手計算での証明は与えられていない。

解答

最大次数と彩色数の関係について。

いわゆる六色問題は，「全ての平面的グラフには5次以下の点がある」ことから証明できる。

更に五色問題も証明できる，ここで次数5の点での扱いがポイント。四色以下ではこの手は通用しないことから，四色問題の難しさは五色問題とは比べ物にならない。

ここからは辺彩色についての定理を2つ紹介する。

二部グラフについては，最大次数と辺彩色数が一致する。

本記事のもくじはこちら：