グラフ彩色
単位距離だけ離れている任意の2つの点が同じ色にならないように平面を彩色する問題 (Hadwiger–Nelson problem) は未解決だが、その彩色数は5、6、7のいずれかだということまでは判明している。その他のグラフの彩色数に関する未解決問題としては、Hadwiger予想(en)がある。これは、彩色数 k のグラフはマイナーとして頂点 k 個の完全グラフを含む、という予想である。また、Erdős–Faber–Lovász予想(en)は、k-クリークが互いに高々1つの頂点を共有する形でk個連結されたグラフはk-彩色的だ、というものである。Albertson予想(en)は、k-彩色的グラフの中で完全グラフが最も交差数が小さい、というものである。
BirkhoffとLewisは四色問題を攻略する手段として彩色多項式を導入し、平面グラフ G の彩色多項式 P ( G , t ) {\displaystyle P(G,t)} は [ 4 , ∞ ) {\displaystyle [4,\infty )} の領域でゼロにならないという予想を立てた。そのような彩色多項式が [ 5 , ∞ ) {\displaystyle [5,\infty )} の領域でゼロにならないことと、 P ( G , 4 ) ≠ 0 {\displaystyle P(G,4)\neq 0} であることは判明しているが、彼らの予想自体は未解決である。任意の2つのグラフの彩色多項式が同一かどうかの判定や、ある多項式が彩色多項式かどうかの判定も未解決の問題である。
グラフ彩色問題は、パターンマッチングなど様々な応用が見つかっている。
数独というパズルも、81個の頂点を持つグラフの9-彩色問題とみなすことができる。
P ( G − u v , k ) {\displaystyle P(G-uv,k)} はそのグラフの彩色の組み合わせ数を表し、u と v が同色の場合もそうでない場合も含まれる。上の式から、彩色の組み合わせ数は2つのグラフの彩色組み合わせ数の和で表される。頂点 u と v の色が異なる場合、u と v が1つの辺で結ばれたグラフでも同じ彩色が可能である。u と v が同色の場合、u と v を縮約したグラフと同じとみなすことができる。W・T・タットはこの漸化式を満たすグラフの属性について興味を持ち、彩色多項式を一般化したタット多項式を発見した。
これらから、再帰的な手続きが考えられ、それを削除・縮約アルゴリズム (deletion–contraction algorithm) と呼び、多くのグラフ彩色アルゴリズムの基盤となっている。すなわち、与えられたグラフを辺が1つ少ない2つのグラフに変換し、それを再帰的に繰り返すのである。これはフィボナッチ数と同様の再帰属性を持ち、最悪でも ( ( 1 + 5 ) / 2 ) n + m = O ( 1.6180 n + m ) {\displaystyle ((1+{\sqrt {5}})/2)^{n+m}=O(1.6180^{n+m})} の処理時間となる。さらに入力されたグラフのスパニング木の数 t ( G ) {\displaystyle t(G)} の多項式の係数を応用することで解析を改善することができる。実際には、分枝限定法を使い、同型のグラフを排除することで再帰回数を減らすことができ、処理時間は2つの頂点を選ぶ際のヒューリスティックに依存する。
頂点彩色が出発点であり、他の彩色問題は頂点彩色に変換可能である。例えば、辺彩色問題は、そのグラフをライングラフに変換したときの頂点彩色と同じであり、面彩色は平面グラフの双対グラフの頂点彩色と同じである。しかし、頂点彩色以外の問題もそのままの形で研究されている。これは、見通しの良さのためでもあり、頂点彩色以外の形式で研究が進んでいるためでもある。
彩色という表現を使うようになったのは、地図を国ごとに彩色する問題が起源である。地図の彩色問題は、平面グラフの面彩色問題に他ならない。また平面グラフの双対性により、頂点彩色問題とも等価であり、あらゆるグラフの問題として一般化できる。数学やコンピュータでは、非負または正の小さい整数を「色」を表現する値として使うことが多い。一般に、任意の有限集合を「色集合」として使うことができる。彩色問題の性質は色数には依存するが、個々の色をどう表すかは関係しない。
グラフ彩色はグラフのラベル付けとは異なる。ラベル付けは数で表される「ラベル」を頂点や辺に割り当てるものである。グラフ彩色問題では、色(を表す数)は任意のマーカーであり、隣接性や結合性に関わる状態を表す。グラフのラベル付け問題では、ラベル(を表す数)は計算可能な値であり、ラベル付けの際の定義で示される何らかの数値的条件を満たす必要がある。
グラフ彩色問題は理論的にも意味があるが、実用的な応用も多い。古典的問題以外にも、色の割り当て方や色自体に異なる制約を加えた問題もある。広く知られているパズルである数独もグラフ彩色問題の変形である。グラフ彩色は研究が盛んな分野のひとつである。
四色定理により、全ての平面グラフは4-彩色可能である。
貪欲彩色法によれば、あらゆるグラフは頂点の最大次数より1つ多い色数で彩色可能である。
χ ( G ) ≤ Δ ( G ) + 1 {\displaystyle \chi (G)\leq \Delta (G)+1\,}
完全グラフは χ ( G ) = n {\displaystyle \chi (G)=n} かつ Δ ( G ) = n − 1 {\displaystyle \Delta (G)=n-1} であり、奇閉路は χ ( G ) = 3 {\displaystyle \chi (G)=3} かつ Δ ( G ) = 2 {\displaystyle \Delta (G)=2} である。したがってこの境界条件はこれらのグラフでは彩色数をよく限定する。それら以外のグラフでは、境界条件をさらに若干改良する余地がある。ブルックスの定理は次の通りである。
ブルックスの定理: 完全グラフでも奇閉路でもない単純な連結グラフ G について χ ( G ) ≤ Δ ( G ) {\displaystyle \chi (G)\leq \Delta (G)} が成り立つ。