グラフ彩色
グラフ G の縮約 G / u v {\displaystyle G/uv} とは、グラフ内の頂点 u と v を特定し、それらの間の辺を全て除去し、その2つの頂点を1つの新たな頂点 w に置き換え、u や v と接合していた全ての辺を w に繋ぎかえることでできるグラフである。この操作はグラフ彩色の解析において重要な役割を演じる。
Zykov (1949) によれば、彩色数は次の漸化式を満たす。
χ ( G ) = min { χ ( G + u v ) , χ ( G / u v ) } {\displaystyle \chi (G)={\text{min}}\{\chi (G+uv),\chi (G/uv)\}}
u と v が隣接した頂点でない場合、 G + u v {\displaystyle G+uv} は辺 u v {\displaystyle uv} を加えたグラフを意味する。この漸化式を評価することに基づくアルゴリズムもいくつかあり、それによって形成される計算木を Zykov 木と呼ぶこともある。実際にかかる時間は頂点 u と v の選択のしかた(ヒューリスティック)に依存する。
彩色多項式は次の漸化式を満たす。
P ( G − u v , k ) = P ( G / u v , k ) + P ( G , k ) {\displaystyle P(G-uv,k)=P(G/uv,k)+P(G,k)}
u と v が隣接した頂点の場合、 G − u v {\displaystyle G-uv} は辺 u v {\displaystyle uv} を除去したグラフを意味する。
グラフの辺彩色とは、グラフの辺を彩色するもので、1つの頂点に接合するそれぞれの辺が常に別々の色になるように最適彩色する。k色を使った辺彩色を「k-辺彩色」と呼び、辺集合をk個のマッチングに分割する問題と等価である。グラフ G の辺彩色に必要な最小の色数を彩色指数 (chromatic index) または辺彩色数 (edge chromatic number) と呼び、χ′(G) で表す。テイト彩色 (Tait coloring) とは、立方体グラフ(3-正則グラフ)の3-辺彩色を意味する。四色定理は、3-正則で辺が交差しない平面グラフをテイト彩色できることと等価である。
k-彩色の判定を力まかせ探索で行う場合、n 個の頂点に k 色を割り当てる k n {\displaystyle k^{n}} の組み合わせを全て試し、制約をみたしているか調べる。彩色数や彩色多項式を計算する場合、力まかせ探索では k = 1 , ... , n − 1 {\displaystyle k=1,\ldots ,n-1} の全ての k について同じ作業をすることになり、小さいグラフ以外では現実的でない。
動的計画法と最大独立集合の数の制約を利用するとk-彩色可能性の判定は時間および空間計算量 O ( 2.445 n ) {\displaystyle O(2.445^{n})} で行える。包除原理と高速ゼータ変換のためのYatesのアルゴリズムを使えば、k-彩色可能性の判定は任意のkについて O ( 2 n n ) {\displaystyle O(2^{n}n)} の時間で行える。3-彩色可能性および4-彩色可能性の判定についてはさらに高速なアルゴリズムが知られており、それぞれ O ( 1.3289 n ) {\displaystyle O(1.3289^{n})} および O ( 1.7504 n ) {\displaystyle O(1.7504^{n})} の時間で判定できる。