彩色という表現を使うようになったのは、地図を国ごとに彩色する問題が起源である。地図の彩色問題は、平面グラフの面彩色問題に他ならない。また平面グラフの双対性により、頂点彩色問題とも等価であり、あらゆるグラフの問題として一般化できる。数学やコンピュータでは、非負または正の小さい整数を「色」を表現する値として使うことが多い。一般に、任意の有限集合を「色集合」として使うことができる。彩色問題の性質は色数には依存するが、個々の色をどう表すかは関係しない。
グラフ彩色はグラフのラベル付けとは異なる。ラベル付けは数で表される「ラベル」を頂点や辺に割り当てるものである。グラフ彩色問題では、色（を表す数）は任意のマーカーであり、隣接性や結合性に関わる状態を表す。グラフのラベル付け問題では、ラベル（を表す数）は計算可能な値であり、ラベル付けの際の定義で示される何らかの数値的条件を満たす必要がある。
グラフ彩色問題は理論的にも意味があるが、実用的な応用も多い。古典的問題以外にも、色の割り当て方や色自体に異なる制約を加えた問題もある。広く知られているパズルである数独もグラフ彩色問題の変形である。グラフ彩色は研究が盛んな分野のひとつである。
歴史.
定義と用語.
頂点彩色.
彩色多項式.
彩色多項式には次のような属性がある。
辺彩色.
属性.
彩色数の境界.
個々の頂点にそれぞれ異なる色を割り当てれば、その彩色は正しい。従って次が成り立つ。
区間グラフでは、この境界がきつい。
彩色数の大きいグラフ.
彩色指数の境界.
さらに次が成り立つ。
一般に、この関係はブルックスの定理が頂点彩色に与える関係よりも強い。
その他の属性.
平面グラフでは、頂点彩色は基本的に と双対関係にある。
無限グラフについては、まだよく判っていない。無限グラフの彩色について判明している数少ない事実として次の事柄がある。
未解決の問題.
アルゴリズム.
多項式時間.
正確なアルゴリズム.
縮約.
 によれば、彩色数は次の漸化式を満たす。
彩色多項式は次の漸化式を満たす。
貪欲彩色.
並列アルゴリズムと分散アルゴリズム.
メッセージをやり取りしない分散アルゴリズム.
計算量.
応用.
スケジューリング.