五色定理
1996年、Robertson, Sanders, Seymour, Thomas は "Efficiently four-coloring planar graphs" の中で、マルチグラフ(英語版)に対する2次多項式時間4彩色アルゴリズムを記述し、同論文の中で彼らは単純平面グラフを線形時間で5色彩色するアルゴリズムについて手短に述べている。これは漸近最適(英語版)であり、また次に述べるウェルニッケの定理(Wernicke's Theorem)に基づく。
ウェルニッケの定理: グラフ G {\displaystyle G} は平面的で、空集合でなく、2辺で囲まれるような面を持たず、かつ頂点の次数の最小値は5であるとする。このとき G {\displaystyle G} には次数が5または6の頂点と隣接しているような次数5の頂点が存在する。
アルゴリズムは、グラフに対し次の2種類の操作を再帰的に用いることで彩色を行う。
次数が4以下である頂点を削除する(この頂点は隣接していた頂点が使っていない色で塗れる)。
次数が5で、かつ次数6以下の頂点と隣接しているような頂点を削除し、隣接していた5頂点の中から辺で結ばれていない2頂点を選び、1頂点に合併(merge)する(合併した2頂点は同じ色で、最初に削除した頂点は隣接していた頂点が使っていない色で塗れる)。
グラフ理論における五色定理(ごしょくていり、英: five color theorem)とは、領域に分けられた平面、例えばある州を郡に分けた政治地図が与えられたとき、5種類以下の色を使って、隣接する領域が必ず別の色になっているように各領域を塗り分けられるという定理である。
五色定理はそれより強い四色定理の系であるが、証明ははるかに易しく、1879年にアルフレッド・ケンプ(英語版)(ケンペとも)が四色定理(予想)を証明し損ねたときの論法に基づき行える。パーシー・ジョン・ヒーウッド(英語版)は11年後にケンプの誤りを発見し、それを元に五色定理を証明した。