グラフ彩色
G の辺彩色は、そのライングラフ L ( G ) {\displaystyle L(G)} の頂点彩色と等価であり、逆も成り立つ。従って、
χ ′ ( G ) = χ ( L ( G ) ) {\displaystyle \chi '(G)=\chi (L(G))\,}
辺彩色可能性とそのグラフの最大次数 Δ ( G ) {\displaystyle \Delta (G)} には強い関連性がある。同じ頂点に接合する全ての辺は異なる色にしなければならないので、次が成り立つ。
χ ′ ( G ) ≥ Δ ( G ) {\displaystyle \chi '(G)\geq \Delta (G)\,}
さらに次が成り立つ。
ケーニグの定理: G が2部グラフなら χ ′ ( G ) = Δ ( G ) {\displaystyle \chi '(G)=\Delta (G)}
一般に、この関係はブルックスの定理が頂点彩色に与える関係よりも強い。
Vizingの定理: 最大次数 Δ {\displaystyle \Delta } のグラフの辺彩色数は Δ {\displaystyle \Delta } または Δ + 1 {\displaystyle \Delta +1} である。
あるグラフが2色で彩色可能かどうかを決定する問題は、そのグラフが2部グラフかどうかの決定問題と等価であり、幅優先探索を使って多項式時間で解ける。より一般化すれば、パーフェクトグラフの彩色数と具体的な彩色は半正定値計画法を使って多項式時間で計算できる。森、弦グラフ、閉路グラフ、車輪グラフ、梯子グラフといった種類のグラフは彩色多項式がわかっているので、多項式時間での評価が可能である。
コンピュータプログラムのコンパイラは、あるプログラミング言語から別の言語への翻訳を行う。その結果生成されるコードの実効効率を向上させるため、レジスタ割り付けというコンパイラ最適化技法が使われる。これは、プログラムで頻繁に使う値を高速なレジスタに保持し続けるようにするものである。理想的には演算に使用する値が常にレジスタに存在することが望ましい。
典型的な技法として、この問題をグラフ彩色問題にモデル化する。コンパイラは頂点をレジスタ(変数)とし、辺を同時に必要とされるレジスタ同士を結ぶように配した干渉グラフを構築する。このグラフがk色で彩色可能なら、k個のレジスタに割り付け可能である。
1912年、彩色問題を研究する過程でジョージ・デビット・バーコフが彩色多項式を導入。これをW・T・タットがタット多項式として一般化し、代数的グラフ理論の重要な構成要素となっている。ケンプは1879年の時点で既に平面グラフ以外のグラフ一般にも言及しており、グラフ彩色のより高次のグラフへの一般化は20世紀初頭から続々となされていった。
1960年、クロード・ベルジュはグラフ彩色についての新たな予想である「強パーフェクトグラフ予想」を定式化した。これは、クロード・シャノンの情報理論の概念であるグラフのゼロエラー容量が発想の元になっている。この予想は40年間証明されなかったが、2002年にChudnovsky、Robertson、Seymour、Thomasが証明し、「強パーフェクトグラフ定理」となった。
1970年ごろから、グラフ彩色についてのアルゴリズムの研究が盛んになってきた。彩色数問題は1972年にリチャード・カープが提案した21のNP完全問題の1つになっており、ほぼ同じころにバックトラッキングや Zykov (1949) の削除・縮約の繰り返し (deletion-contraction recurrence) などに基づいた指数関数時間の様々なアルゴリズムが開発された。グラフ彩色の応用の1つとしてコンパイラにおけるレジスタ割り付けがあり、1981年に登場した。