グラフ彩色
個々の頂点にそれぞれ異なる色を割り当てれば、その彩色は正しい。従って次が成り立つ。
1 ≤ χ ( G ) ≤ n {\displaystyle 1\leq \chi (G)\leq n\,}
1-彩色可能なのは辺のないグラフに限られる。n個の頂点を持つ完全グラフ K n {\displaystyle K_{n}} を彩色するには χ ( K n ) = n {\displaystyle \chi (K_{n})=n} 色が必要である。最適な彩色では、グラフ内の m 個以上の辺が色クラス間を結ぶ位置にある。従って、次が成り立つ。
χ ( G ) ( χ ( G ) − 1 ) ≤ 2 m {\displaystyle \chi (G)(\chi (G)-1)\leq 2m\,}
G に大きさ k のクリークが含まれている場合、そのクリークの彩色に少なくとも k 色を必要とする。言い換えれば、グラフ G の彩色数について次が成り立つ。
χ ( G ) ≥ ω ( G ) {\displaystyle \chi (G)\geq \omega (G)\,}
区間グラフでは、この境界がきつい。
2-彩色可能なグラフは常に2部グラフであり、木や森もそれに含まれる。
グラフ彩色は、地図の色分けの形で始まったものであり、当初はほとんど平面グラフだけを対象としていた。イングランドの地図をカウンティごとに色分けしようとしたフランシス・ガスリーは、4色あればどの境界線も両側が同じ色になることがないよう色分けできることに気づき、四色定理を主張した。ガスリーの兄弟がこの問題を数学の先生だったユニヴァーシティ・カレッジ・ロンドンのオーガスタス・ド・モルガンに提示してみたところ、彼は1852年にウィリアム・ローワン・ハミルトンへの手紙でこの問題に言及した。1879年、ロンドン数学会の会合でアーサー・ケイリーがこの問題を提示した。同年、アルフレッド・ケンプがその証明をしたとする論文を発表し、その後10年ほどはこの問題は証明済みとみなされていた。この業績によってケンプは王立協会フェローに選ばれ、後にロンドン数学会の会長に就任している。
1890年、パーシー・ヘイウッドはケンプの証明が間違っていることを指摘した。ケンプの証明は地図の塗りわけに「五色」あれば十分であることを示したに過ぎなかった。その後約1世紀に渡って四色定理を証明すべく様々な努力がなされ、とうとう1976年にケネス・アッペルとヴォルフガング・ハーケンが証明した。驚くべきことに、その証明の考え方はヘイウッドやケンプの考え方に沿ったもので、途中の数十年間の様々な努力は無視されている。四色定理の証明では初めて大規模にコンピュータを利用したことも注目に値する。