グラフ彩色
彩色多項式(chromatic polynomial)とは、与えられたグラフを与えられた色数内で彩色したときの彩色の組合せ数を求める式である。例えば、右図のグラフは3色で彩色すると12通りの彩色が可能である。2色では彩色できない。4色では 24 + 4×12 = 72 通りである。4色を使った彩色は24通りで、4色のうちの3色を使った彩色はそれぞれ12通りなので、このような計算になる(4色を4つの頂点に割り当てる場合は、任意の組み合わせが可能である)。従って、このグラフの彩色数を表にすると次のようになる。
彩色多項式は、 P ( G , t ) {\displaystyle P(G,t)} で表され、グラフ G {\displaystyle G} を t {\displaystyle t} 色で彩色したときの色の組合せ数である。名前が示すとおり、ある G {\displaystyle G} についての彩色多項式は、 t {\displaystyle t} に関する多項式となる。例に挙げたグラフでは、 P ( G , t ) = t ( t − 1 ) 2 ( t − 2 ) {\displaystyle P(G,t)=t(t-1)^{2}(t-2)} となる。
彩色多項式は彩色数と共に、 G {\displaystyle G} の彩色可能性についての情報をもたらす。実際、彩色数 χ は彩色多項式の根ではない最小の正の整数である。
貪欲法では、頂点に所定の順序 v 1 {\displaystyle v_{1}} ,..., v n {\displaystyle v_{n}} を設定し、 v i {\displaystyle v_{i}} に対して v 1 {\displaystyle v_{1}} ,..., v i − 1 {\displaystyle v_{i-1}} までの隣接する頂点で使っていない色を設定し、それまでに使ったどの色の頂点とも隣接している場合は、新たな色を設定する。結果は頂点をどう順序付けするかに依存し、彩色数 χ ( G ) {\displaystyle \chi (G)} による最適彩色を導き出す順序付けも存在することがある。しかし、順序付けによってはもっと悪い結果になる。例えば頂点が n 個の crown graph は2-彩色的だが、貪欲彩色では n / 2 {\displaystyle n/2} 色を必要とすることがある。
平面グラフでは、頂点彩色は基本的に nowhere-zero flow と双対関係にある。
無限グラフについては、まだよく判っていない。無限グラフの彩色について判明している数少ない事実として次の事柄がある。
無限グラフ G の全ての有限部分グラフが k-彩色可能であれば、選択公理を仮定した場合にG自体も同様である(de Bruijn & Erdős 1951)。
また、n ≥ n0 の n 色全部を使って彩色可能なグラフは、無限完全彩色可能である(Fawcett 1978)。
グラフ彩色は困難である。k = 1 および k = 2 以外の k について「与えられたグラフがk-彩色可能か」という決定問題はNP完全問題である。彩色数を求める問題はNP困難である。彩色可能性を問う決定問題は次数が最大4の平面グラフであってもNP完全である。
既知の最良の近似アルゴリズムはオーダー O(n(log n)(log log n)) の近似精度で彩色数を計算する。あらゆる ε > 0 について、n 以内に彩色数を近似することはNP困難である。
3-彩色可能なグラフを4色で彩色する問題もNP困難であり、k-彩色可能なグラフを k 色で彩色する問題も k が十分大きければNP困難である。
彩色多項式の係数を求める問題は#P困難である。実際 k = 1 または k = 2 以外の任意の有理数 k について χ ( G , k ) {\displaystyle \chi (G,k)} を求める計算も#P困難である。NP = RP でない限り、k = 2 以外の k ≥ 1.5 の有理数 k について彩色多項式を評価する多項式時間の近似アルゴリズムは存在しない。
辺彩色については、Vizingの証明の結果から最大 Δ+1 色で彩色するアルゴリズムが得られている。しかし、2つの候補値から辺彩色数を決定する問題はNP完全である。近似アルゴリズムの場合、Vizingの辺彩色数を求めるアルゴリズムの近似度は4/3であり、任意の ε > 0 について(4/3 − ε )-近似アルゴリズムは存在しない(P=NPでない限り)。これらは近似アルゴリズムについての最も古い論文である(近似度という記法は明確には使っていない)。