グラフ彩色

3色に頂点彩色（最適彩色）されたグラフ。ピーターセングラフの彩色数は3である。

グラフ彩色（グラフさいしょく、英: Graph coloring）とは、グラフの何らかの要素に、ある制約条件を満たすように色を割り当てることである。最も単純なものは、隣接する頂点同士が同じ色にならないように全頂点に彩色する問題である。これを頂点彩色（ちょうてんさいしょく）という。同様に辺彩色（へんさいしょく）は、隣接する辺同士が同じ色にならないように全辺を彩色する問題、面彩色（めんさいしょく）は、平面グラフの辺で囲まれた各領域（面）を隣接する面同士が同じ色にならないように彩色する問題である。

概要

頂点彩色が出発点であり、他の彩色問題は頂点彩色に変換可能である。例えば、辺彩色問題は、そのグラフをライングラフに変換したときの頂点彩色と同じであり、面彩色は平面グラフの双対グラフの頂点彩色と同じである。しかし、頂点彩色以外の問題もそのままの形で研究されている。これは、見通しの良さのためでもあり、頂点彩色以外の形式で研究が進んでいるためでもある。

彩色という表現を使うようになったのは、地図を国ごとに彩色する問題が起源である。地図の彩色問題は、平面グラフの面彩色問題に他ならない。また平面グラフの双対性により、頂点彩色問題とも等価であり、あらゆるグラフの問題として一般化できる。数学やコンピュータでは、非負または正の小さい整数を「色」を表現する値として使うことが多い。一般に、任意の有限集合を「色集合」として使うことができる。彩色問題の性質は色数には依存するが、個々の色をどう表すかは関係しない。

グラフ彩色はグラフのラベル付けとは異なる。ラベル付けは数で表される「ラベル」を頂点や辺に割り当てるものである。グラフ彩色問題では、色（を表す数）は任意のマーカーであり、隣接性や結合性に関わる状態を表す。グラフのラベル付け問題では、ラベル（を表す数）は計算可能な値であり、ラベル付けの際の定義で示される何らかの数値的条件を満たす必要がある。

グラフ彩色問題は理論的にも意味があるが、実用的な応用も多い。古典的問題以外にも、色の割り当て方や色自体に異なる制約を加えた問題もある。広く知られているパズルである数独もグラフ彩色問題の変形である。グラフ彩色は研究が盛んな分野のひとつである。

歴史

→「四色定理 § 歴史」も参照

グラフ彩色は、地図の色分けの形で始まったものであり、当初はほとんど平面グラフだけを対象としていた。イングランドの地図をカウンティごとに色分けしようとしたフランシス・ガスリーは、4色あればどの境界線も両側が同じ色になることがないよう色分けできることに気づき、四色定理を主張した。ガスリーの兄弟がこの問題を数学の先生だったユニヴァーシティ・カレッジ・ロンドンのオーガスタス・ド・モルガンに提示してみたところ、彼は1852年にウィリアム・ローワン・ハミルトンへの手紙でこの問題に言及した。1879年、ロンドン数学会の会合でアーサー・ケイリーがこの問題を提示した。同年、アルフレッド・ケンプがその証明をしたとする論文を発表し、その後10年ほどはこの問題は証明済みとみなされていた。この業績によってケンプは王立協会フェローに選ばれ、後にロンドン数学会の会長に就任している[1]。

1890年、パーシー・ヘイウッドはケンプの証明が間違っていることを指摘した。ケンプの証明は地図の塗りわけに「五色」あれば十分であることを示したに過ぎなかった。その後約1世紀に渡って四色定理を証明すべく様々な努力がなされ、とうとう1976年にケネス・アッペルとヴォルフガング・ハーケンが証明した。驚くべきことに、その証明の考え方はヘイウッドやケンプの考え方に沿ったもので、途中の数十年間の様々な努力は無視されている[2]。四色定理の証明では初めて大規模にコンピュータを利用したことも注目に値する。

1912年、彩色問題を研究する過程でジョージ・デビット・バーコフが彩色多項式を導入。これをW・T・タットがタット多項式として一般化し、代数的グラフ理論の重要な構成要素となっている。ケンプは1879年の時点で既に平面グラフ以外のグラフ一般にも言及しており[3]、グラフ彩色のより高次のグラフへの一般化は20世紀初頭から続々となされていった。

1960年、クロード・ベルジュはグラフ彩色についての新たな予想である「強パーフェクトグラフ予想」を定式化した。これは、クロード・シャノンの情報理論の概念であるグラフのゼロエラー容量が発想の元になっている。この予想は40年間証明されなかったが、2002年にChudnovsky、Robertson、Seymour、Thomasが証明し、「強パーフェクトグラフ定理」となった。

1970年ごろから、グラフ彩色についてのアルゴリズムの研究が盛んになってきた。彩色数問題は1972年にリチャード・カープが提案した21のNP完全問題の1つになっており、ほぼ同じころにバックトラッキングや Zykov (1949) の削除・縮約の繰り返し (deletion-contraction recurrence) などに基づいた指数関数時間の様々なアルゴリズムが開発された。グラフ彩色の応用の1つとしてコンパイラにおけるレジスタ割り付けがあり、1981年に登場した。

定義と用語

頂点彩色

単にグラフの彩色(coloring)と言った場合、「頂点彩色」を意味することが多い。また、隣接する頂点が同じ色にならないよう彩色すること、すなわち最適彩色を意味する。隣接する頂点とは、同じ辺と接している頂点である。ある頂点から同じ頂点へ戻る辺（ループ）が存在する場合、頂点彩色問題は決して最適解を持たないので、以下ではループがないグラフのみを扱う。

頂点のラベルを「色」で表すのは地図の塗りわけに起源がある。「赤」や「青」といったラベルは色数が小さい場合のみ使われ、一般にはラベルとして整数 {1,2,3,...} を使う。

最大 k 色を使った彩色を k-彩色と言う。グラフ G の彩色に必要な最小の色数を彩色数(chromatic number)と呼び χ(G) で表す。例えば、n 個の頂点からなる完全グラフ（あらゆる頂点間に辺があるグラフ）${\displaystyle K_{n}}$ の彩色数は、${\displaystyle \chi (K_{n})=n}$ である。k-彩色できるグラフをk-彩色可能(k-colorable)といい、そのkがそのグラフの彩色数であるとき、k-彩色的(k-chromatic)という。同じ色が割り当てられた頂点の集合を「色クラス」と呼び、色クラス同士は独立集合となっている。したがって、k-彩色することは、頂点集合を k 個の独立部分集合に分割するのと等価であり、k-部 (k-partite) グラフや k-彩色可能といった用語も同じ意味を持つ。

彩色多項式

このグラフは3色で12通りの彩色が可能。P(G,t)(t=3)= t(t-1)^2(t-2)=12。三角形グラフt(t-1)(t-2)と、そこに接続される1次の頂点(t-1)の積として求められる。

彩色多項式(chromatic polynomial)とは、与えられたグラフを与えられた色数内で彩色したときの彩色の組合せ数を求める式である。例えば、右図のグラフは3色で彩色すると12通りの彩色が可能である。2色では彩色できない。4色では 24 + 4×12 = 72 通りである。4色を使った彩色は24通りで、4色のうちの3色を使った彩色はそれぞれ12通りなので、このような計算になる（4色を4つの頂点に割り当てる場合は、任意の組み合わせが可能である）。従って、このグラフの彩色数を表にすると次のようになる。

色数	1	2	3	4	…
彩色の組み合わせ数	0	0	12	72	…

彩色多項式は、${\displaystyle P(G,t)}$ で表され、グラフ ${\displaystyle G}$ を ${\displaystyle t}$ 色で彩色したときの色の組合せ数である。名前が示すとおり、ある ${\displaystyle G}$ についての彩色多項式は、${\displaystyle t}$ に関する多項式となる。例に挙げたグラフでは、${\displaystyle P(G,t)=t(t-1)^{2}(t-2)}$ となる。

彩色多項式は彩色数と共に、${\displaystyle G}$ の彩色可能性についての情報をもたらす。実際、彩色数 χ は彩色多項式の根ではない最小の正の整数である。

${\displaystyle \chi (G)=\min\{k\colon P(G,k)>0\}}$

この概念を最初に使ったのは George David Birkhoff と D. C. Lewis であり、四色定理の証明を試みる過程で用いた。

特定のグラフに関する彩色多項式

三角形 ${\displaystyle K_{3}}$	${\displaystyle t(t-1)(t-2)}$
完全グラフ ${\displaystyle K_{n}}$	${\displaystyle t(t-1)(t-2)}$...${\displaystyle (t-(n-1))}$
${\displaystyle n}$ 頂点の木	${\displaystyle t(t-1)^{n-1}}$
閉路グラフ ${\displaystyle C_{n}}$	${\displaystyle (t-1)^{n}+(-1)^{n}(t-1)}$
ピーターセングラフ	${\displaystyle t(t-1)(t-2)(t^{7}-12t^{6}+67t^{5}-230t^{4}+529t^{3}-814t^{2}+775t-352)}$

彩色多項式には次のような属性がある。

• ${\displaystyle P(G,0)=0}$
• ${\displaystyle P(G,1)=0}$ （${\displaystyle G}$ に辺がある場合）
• ${\displaystyle P(G,t)=0}$（${\displaystyle t<\chi (G)}$ の場合）
• ${\displaystyle G}$ が ${\displaystyle n}$ 個の頂点、${\displaystyle m}$ 個の辺、${\displaystyle k}$ 個の連結成分 ${\displaystyle G_{1},G_{2},}$…,${\displaystyle G_{k}}$ から成るとき、
  • ${\displaystyle P(G,t)}$ の次数は ${\displaystyle n}$ である。
  • ${\displaystyle P(G,t)}$ における ${\displaystyle t^{n}}$ の係数は 1 である。
  • ${\displaystyle P(G,t)}$ における ${\displaystyle t^{n-1}}$ の係数は ${\displaystyle -m}$ である。
  • ${\displaystyle t^{0},t^{1},}$ … ${\displaystyle t^{k-1}}$ の係数は全てゼロである。
  • ${\displaystyle t^{k}}$ の係数はゼロではない。
  • ${\displaystyle P(G,t)=P(G_{1},t)P(G_{2},t)}$⋯${\displaystyle P(G_{k},t)}$
• 全ての彩色多項式の係数は符号が交互に変化する。
• ${\displaystyle P(G,t)=t(t-1)^{n-1}}$ であるときのみ、${\displaystyle n}$ 頂点のグラフ G は木である。
• 単位元で評価された導関数 ${\displaystyle P'(G,1)}$ は「彩色不変量(chromatic invariant)」${\displaystyle \theta (G)}$ である。

辺彩色

グラフの辺彩色とは、グラフの辺を彩色するもので、1つの頂点に接合するそれぞれの辺が常に別々の色になるように最適彩色する。k色を使った辺彩色を「k-辺彩色」と呼び、辺集合をk個のマッチングに分割する問題と等価である。グラフ G の辺彩色に必要な最小の色数を彩色指数 (chromatic index) または辺彩色数 (edge chromatic number) と呼び、χ′(G) で表す。テイト彩色 (Tait coloring) とは、立方体グラフ（3-正則グラフ）の3-辺彩色を意味する。四色定理は、3-正則で辺が交差しない平面グラフをテイト彩色できることと等価である。

属性

彩色数の境界

個々の頂点にそれぞれ異なる色を割り当てれば、その彩色は正しい。従って次が成り立つ。

${\displaystyle 1\leq \chi (G)\leq n\,}$

1-彩色可能なのは辺のないグラフに限られる。n個の頂点を持つ完全グラフ ${\displaystyle K_{n}}$ を彩色するには ${\displaystyle \chi (K_{n})=n}$ 色が必要である。最適な彩色では、グラフ内の m 個以上の辺が色クラス間を結ぶ位置にある。従って、次が成り立つ。

${\displaystyle \chi (G)(\chi (G)-1)\leq 2m\,}$

G に大きさ k のクリークが含まれている場合、そのクリークの彩色に少なくとも k 色を必要とする。言い換えれば、グラフ G の彩色数について次が成り立つ。

${\displaystyle \chi (G)\geq \omega (G)\,}$

区間グラフでは、この境界がきつい。

2-彩色可能なグラフは常に2部グラフであり、木や森もそれに含まれる。四色定理により、全ての平面グラフは4-彩色可能である。

貪欲彩色法によれば、あらゆるグラフは頂点の最大次数より1つ多い色数で彩色可能である。

${\displaystyle \chi (G)\leq \Delta (G)+1\,}$

完全グラフは ${\displaystyle \chi (G)=n}$ かつ ${\displaystyle \Delta (G)=n-1}$ であり、奇閉路は ${\displaystyle \chi (G)=3}$ かつ ${\displaystyle \Delta (G)=2}$ である。したがってこの境界条件はこれらのグラフでは彩色数をよく限定する。それら以外のグラフでは、境界条件をさらに若干改良する余地がある。ブルックスの定理[4]は次の通りである。

ブルックスの定理: 完全グラフでも奇閉路でもない単純な連結グラフ G について ${\displaystyle \chi (G)\leq \Delta (G)}$ が成り立つ。

彩色数の大きいグラフ

最大クリークの大きなグラフは彩色数も大きいが、逆は必ずしも真ではない。Grötzschグラフ(en)は4-彩色的だが、三角形を含まない（クリークがない）。それを一般化したグラフをMycielskianと呼ぶ。

Mycielskiの定理[5]: 三角形を含まない、任意の彩色数のグラフが存在する。

ブルックスの定理から、彩色数の大きいグラフは次数が高くなければならない。また、局所的には大きなクリークがあれば彩色数は大きくなる。しかし、彩色可能性はグラフの局所的現象ではない。内周（最短閉路の長さ）が大きいグラフは、局所的に見れば木のようになっているが、その彩色数は2になるとは限らない。

定理（エルデシュ）: 任意の内周が大きくかつ彩色数の大きいグラフが存在する。

彩色指数の境界

G の辺彩色は、そのライングラフ ${\displaystyle L(G)}$ の頂点彩色と等価であり、逆も成り立つ。従って、

${\displaystyle \chi '(G)=\chi (L(G))\,}$

辺彩色可能性とそのグラフの最大次数 ${\displaystyle \Delta (G)}$ には強い関連性がある。同じ頂点に接合する全ての辺は異なる色にしなければならないので、次が成り立つ。

${\displaystyle \chi '(G)\geq \Delta (G)\,}$

さらに次が成り立つ。

ケーニグの定理: G が2部グラフなら ${\displaystyle \chi '(G)=\Delta (G)}$

一般に、この関係はブルックスの定理が頂点彩色に与える関係よりも強い。

Vizingの定理: 最大次数 ${\displaystyle \Delta }$ のグラフの辺彩色数は ${\displaystyle \Delta }$ または ${\displaystyle \Delta +1}$ である。

その他の属性

平面グラフでは、頂点彩色は基本的に nowhere-zero flow と双対関係にある。

無限グラフについては、まだよく判っていない。無限グラフの彩色について判明している数少ない事実として次の事柄がある。

無限グラフ G の全ての有限部分グラフが k-彩色可能であれば、選択公理を仮定した場合にG自体も同様である(de Bruijn & Erdős 1951)。

また、n ≥ n₀ の n 色全部を使って彩色可能なグラフは、無限完全彩色可能である(Fawcett 1978)。

未解決の問題

単位距離だけ離れている任意の2つの点が同じ色にならないように平面を彩色する問題 (Hadwiger–Nelson problem) は未解決だが、その彩色数は5、6、7のいずれかだということまでは判明している[6]。その他のグラフの彩色数に関する未解決問題としては、Hadwiger予想(en)がある。これは、彩色数 k のグラフはマイナーとして頂点 k 個の完全グラフを含む、という予想である。また、Erdős–Faber–Lovász予想(en)は、k-クリークが互いに高々1つの頂点を共有する形でk個連結されたグラフはk-彩色的だ、というものである。Albertson予想(en)は、k-彩色的グラフの中で完全グラフが最も交差数が小さい、というものである。

BirkhoffとLewisは四色問題を攻略する手段として彩色多項式を導入し、平面グラフ G の彩色多項式 ${\displaystyle P(G,t)}$ は ${\displaystyle [4,\infty )}$ の領域でゼロにならないという予想を立てた。そのような彩色多項式が ${\displaystyle [5,\infty )}$ の領域でゼロにならないことと、${\displaystyle P(G,4)\neq 0}$ であることは判明しているが、彼らの予想自体は未解決である。任意の2つのグラフの彩色多項式が同一かどうかの判定や、ある多項式が彩色多項式かどうかの判定も未解決の問題である。

アルゴリズム

グラフ彩色
決定問題
名称	グラフ彩色、頂点彩色、k-彩色
入力	n 個の頂点を持つグラフ G。整数 k
出力	G は k 個の色で最適彩色可能か?
時間計算量	O(2^nn)[7]
複雑性クラス	NP完全
還元	3-SAT
Garey–Johnson	GT4
最適化問題
名称	彩色数
入力	n 個の頂点を持つグラフ G
出力	χ(G)
複雑性クラス	NP困難
近似計算量	O(n (log n)^−3(log log n)^2)
非近似計算量	O(n^1−ε) - P=NPでない場合
数え上げ問題
名称	彩色多項式
入力	n 個の頂点を持つグラフ G。整数 k
出力	G を k-彩色する場合の P (G,k) の値
時間計算量	O(2^nn)
複雑性クラス	#P完全
近似計算量	多項式時間 - 一部のケースのみ
非近似計算量	P=NPでない場合、多項式時間アルゴリズムは存在しない。

多項式時間

あるグラフが2色で彩色可能かどうかを決定する問題は、そのグラフが2部グラフかどうかの決定問題と等価であり、幅優先探索を使って多項式時間で解ける。より一般化すれば、パーフェクトグラフの彩色数と具体的な彩色は半正定値計画法を使って多項式時間で計算できる。森、弦グラフ、閉路グラフ、車輪グラフ、梯子グラフといった種類のグラフは彩色多項式がわかっているので、多項式時間での評価が可能である。

正確なアルゴリズム

k-彩色の判定を力まかせ探索で行う場合、n 個の頂点に k 色を割り当てる ${\displaystyle k^{n}}$ の組み合わせを全て試し、制約をみたしているか調べる。彩色数や彩色多項式を計算する場合、力まかせ探索では ${\displaystyle k=1,\ldots ,n-1}$ の全ての k について同じ作業をすることになり、小さいグラフ以外では現実的でない。

動的計画法と最大独立集合の数の制約を利用するとk-彩色可能性の判定は時間および空間計算量 ${\displaystyle O(2.445^{n})}$ で行える[8]。包除原理と高速ゼータ変換のためのYatesのアルゴリズムを使えば、k-彩色可能性の判定は任意のkについて ${\displaystyle O(2^{n}n)}$ の時間で行える[7]。3-彩色可能性および4-彩色可能性の判定についてはさらに高速なアルゴリズムが知られており、それぞれ ${\displaystyle O(1.3289^{n})}$[9] および ${\displaystyle O(1.7504^{n})}$[10] の時間で判定できる。

縮約

グラフ G の縮約 ${\displaystyle G/uv}$ とは、グラフ内の頂点 u と v を特定し、それらの間の辺を全て除去し、その2つの頂点を1つの新たな頂点 w に置き換え、u や v と接合していた全ての辺を w に繋ぎかえることでできるグラフである。この操作はグラフ彩色の解析において重要な役割を演じる。

Zykov (1949) によれば、彩色数は次の漸化式を満たす。

${\displaystyle \chi (G)={\text{min}}\{\chi (G+uv),\chi (G/uv)\}}$

u と v が隣接した頂点でない場合、${\displaystyle G+uv}$ は辺 ${\displaystyle uv}$ を加えたグラフを意味する。この漸化式を評価することに基づくアルゴリズムもいくつかあり、それによって形成される計算木を Zykov 木と呼ぶこともある。実際にかかる時間は頂点 u と v の選択のしかた（ヒューリスティック）に依存する。

彩色多項式は次の漸化式を満たす。

${\displaystyle P(G-uv,k)=P(G/uv,k)+P(G,k)}$

u と v が隣接した頂点の場合、${\displaystyle G-uv}$ は辺 ${\displaystyle uv}$ を除去したグラフを意味する。${\displaystyle P(G-uv,k)}$ はそのグラフの彩色の組み合わせ数を表し、u と v が同色の場合もそうでない場合も含まれる。上の式から、彩色の組み合わせ数は2つのグラフの彩色組み合わせ数の和で表される。頂点 u と v の色が異なる場合、u と v が1つの辺で結ばれたグラフでも同じ彩色が可能である。u と v が同色の場合、u と v を縮約したグラフと同じとみなすことができる。W・T・タットはこの漸化式を満たすグラフの属性について興味を持ち、彩色多項式を一般化したタット多項式を発見した。

これらから、再帰的な手続きが考えられ、それを削除・縮約アルゴリズム (deletion–contraction algorithm) と呼び、多くのグラフ彩色アルゴリズムの基盤となっている。すなわち、与えられたグラフを辺が1つ少ない2つのグラフに変換し、それを再帰的に繰り返すのである。これはフィボナッチ数と同様の再帰属性を持ち、最悪でも ${\displaystyle ((1+{\sqrt {5}})/2)^{n+m}=O(1.6180^{n+m})}$ の処理時間となる[11]。さらに入力されたグラフのスパニング木の数 ${\displaystyle t(G)}$ の多項式の係数を応用することで解析を改善することができる[12]。実際には、分枝限定法を使い、同型のグラフを排除することで再帰回数を減らすことができ、処理時間は2つの頂点を選ぶ際のヒューリスティックに依存する。

貪欲彩色

同じグラフにおいて2種類の頂点の順序付けをしたときの貪欲彩色。うまく順序付けすれば2-彩色可能だが、貪欲彩色では ${\displaystyle n/2}$ 色まで費やすことがある。

貪欲法では、頂点に所定の順序 ${\displaystyle v_{1}}$,…,${\displaystyle v_{n}}$ を設定し、${\displaystyle v_{i}}$ に対して ${\displaystyle v_{1}}$,…,${\displaystyle v_{i-1}}$ までの隣接する頂点で使っていない色を設定し、それまでに使ったどの色の頂点とも隣接している場合は、新たな色を設定する。結果は頂点をどう順序付けするかに依存し、彩色数 ${\displaystyle \chi (G)}$ による最適彩色を導き出す順序付けも存在することがある。しかし、順序付けによってはもっと悪い結果になる。例えば頂点が n 個の crown graph は2-彩色的だが、貪欲彩色では ${\displaystyle n/2}$ 色を必要とすることがある。

頂点を次数が小さくなる順序でソートすれば、貪欲彩色で使う最大色数は ${\displaystyle {\text{max}}_{i}{\text{ min}}\{d(x_{i})+1,i\}}$ となり、最悪でもそのグラフの最大次数より1つだけ大きい色数になる。このヒューリスティックを Welsh–Powell アルゴリズムとも呼ぶ[13]。他にも、アルゴリズム実行中に動的に頂点の順序を決定していくヒューリスティックもあり、最も多くの異なる色と隣接している頂点を次の頂点として選ぶという方法もある[14]。他にも様々なヒューリスティクスを採用したアルゴリズムがあり、これらを総称して逐次彩色 (sequential coloring) アルゴリズムと呼ぶこともある。

並列アルゴリズムと分散アルゴリズム

グラフ彩色の分散アルゴリズムは、グラフの「対称性の破れ」の問題と密接に関連する。対称グラフでは、決定的分散アルゴリズムでは最適彩色を見つけることができない。対称性の破れを見つけるには何らかの予備的情報を必要とする。一般的な前提条件として、n 個の各頂点に {1, 2, ..., n} の一意の識別子を付与した状態、つまりそれぞれが別々の色に彩色された状態を初期状態とする。したがって、なすべきことは n 色を例えば Δ + 1 色にまで減らしていくことである。

貪欲法を単純に分散アルゴリズム化して(Δ + 1)-彩色を求めるアルゴリズムは、最悪の場合 Θ(n) 回の通信を必要とし、情報をネットワークの一端から全体に伝播させる必要があることもある。ただし、最大次数 Δ が小さければ、もっと高速なアルゴリズムも存在する。

単純で興味深い例として n-閉路グラフがある。Richard Cole と Uzi Vishkin[15]によれば、1回の同期通信ステップで色数を n から O(log n) に減らす分散アルゴリズムが存在する。これを繰り返すとn-閉路グラフの3-彩色を O(log* n) の通信ステップで得ることができる（各頂点には一意の識別子が付与されていることが前提）。

反復対数関数 log* は成長が非常にゆっくりとしていて、ほぼ定数とみなせる。そこで Cole と Vishkin の成果から、n-閉路の3-彩色を求める定数時間の分散アルゴリズムはあるのかという問題が提起される。Linial (1992) によれば、そのようなアルゴリズムは存在しない。決定的分散アルゴリズムはn-閉路をn-彩色から3-彩色に減らすのに Ω(log* n)の通信ステップを必要とする。

ColeとVishkinの技法は任意の次数の制限されたグラフに適用可能である。その場合の計算時間は poly(Δ) + O(log* n) となる[16]。(Δ + 1)-彩色の既知の最高速アルゴリズムとしては、Leonid Barenboim と Michael Elkin のものがある。その計算時間は O(Δ) + log*(n)/2 であり[17]、Linialの下限によれば 1/2 という係数はこれ以上改善できないので n に対して最適なアルゴリズムということになる。

辺彩色の分散アルゴリズムも研究されてきた。Panconesi & Rizzi (2001) では、(2Δ − 1)-辺彩色を O(Δ + log* n) の時間で可能なアルゴリズムが示されている。Linial (1992) による分散頂点彩色の下限は、辺彩色問題についても同様に成り立つ。

メッセージをやり取りしない分散アルゴリズム

メッセージのやり取りをしない分散アルゴリズム (decentralized algorithm) もある。最適彩色が存在するグラフについて、効率的にそれを求めるアルゴリズムが存在する。この場合、各頂点は隣接する頂点が自分と同じ色かどうかをメッセージをやり取りせずに確認できることを前提とする。例えば無線のチャンネル割り当てなどでは、他の通信機が同じチャンネルを使っているかどうかは容易に検出可能なので、この前提は穏当である。そのような情報があれば、学習するオートマトンが確実なグラフ彩色を見出すのに十分である[18]。

計算量

グラフ彩色は困難である。k = 1 および k = 2 以外の k について「与えられたグラフがk-彩色可能か」という決定問題はNP完全問題である。彩色数を求める問題はNP困難である。彩色可能性を問う決定問題は次数が最大4の平面グラフであってもNP完全である[19]。

既知の最良の近似アルゴリズムはオーダー O(n(log n)^−3(log log n)^2) の近似精度で彩色数を計算する[20]。あらゆる ε > 0 について、n^1−ε 以内に彩色数を近似することはNP困難である[21]。

3-彩色可能なグラフを4色で彩色する問題もNP困難であり[22]、k-彩色可能なグラフを k^(log k ) / 25 色で彩色する問題も k が十分大きければNP困難である[23]。

彩色多項式の係数を求める問題は#P困難である。実際 k = 1 または k = 2 以外の任意の有理数 k について ${\displaystyle \chi (G,k)}$ を求める計算も#P困難である[24]。NP = RP でない限り、k = 2 以外の k ≥ 1.5 の有理数 k について彩色多項式を評価する多項式時間の近似アルゴリズムは存在しない[25]。

辺彩色については、Vizingの証明の結果から最大 Δ+1 色で彩色するアルゴリズムが得られている。しかし、2つの候補値から辺彩色数を決定する問題はNP完全である[26]。近似アルゴリズムの場合、Vizingの辺彩色数を求めるアルゴリズムの近似度は4/3であり、任意の ε > 0 について(4/3 − ε )-近似アルゴリズムは存在しない（P=NPでない限り）。これらは近似アルゴリズムについての最も古い論文である（近似度という記法は明確には使っていない）[27]。

応用

スケジューリング

頂点彩色は各種スケジューリング問題のモデルとなる[28]。最も単純化したスケジューリング問題は、一連の仕事を時間割にひとつずつ（ある時間には1つの仕事だけをするように）あてはめていくものである。個々の仕事にはリソースの競合など同時に実施できない制約条件がある。これをグラフで表すと、個々の仕事が頂点、競合する仕事を結ぶ線が辺となる。このグラフの彩色数を求める問題は、全部の仕事が終わるまでにかかる時間を最小にすることと等価である。

スケジューリング問題の詳細がそのグラフの構造を定義する。例えば航空機の運航スケジューリングの場合、インターバルグラフで表せば効率的に彩色問題として解ける。無線局の帯域幅割り当ての場合、単位円グラフで表せばよい。

レジスタ割り付け

→詳細は「レジスタ割り付け」を参照

コンピュータプログラムのコンパイラは、あるプログラミング言語から別の言語への翻訳を行う。その結果生成されるコードの実効効率を向上させるため、レジスタ割り付けというコンパイラ最適化技法が使われる。これは、プログラムで頻繁に使う値を高速なレジスタに保持し続けるようにするものである。理想的には演算に使用する値が常にレジスタに存在することが望ましい。

典型的な技法として、この問題をグラフ彩色問題にモデル化する[29]。コンパイラは頂点をレジスタ（変数）とし、辺を同時に必要とされるレジスタ同士を結ぶように配した干渉グラフを構築する。このグラフがk色で彩色可能なら、k個のレジスタに割り付け可能である。

その他

グラフ彩色問題は、パターンマッチングなど様々な応用が見つかっている。

数独というパズルも、81個の頂点を持つグラフの9-彩色問題とみなすことができる。

脚注・出典

1. M. Kubale, History of graph coloring, in Kubale (2004)
2. van Lint & Wilson (2001, Chap. 33)
3. Jensen & Toft (1995, p. 2)
4. Brooks (1941)
5. Mycielski (1955)
6. Heule, Marijn J.H. (2018), Computing Small Unit-Distance Graphs with Chromatic Number 5, arXiv:1805.12181, Bibcode: 2018arXiv180512181H 
7. ^ Björklund, Husfeldt & Koivisto (2006)
8. Lawler (1976)
9. Beigel & Eppstein (2005)
10. Byskov (2004)
11. Wilf (1986)
12. Sekine, Imai & Tani (1995)
13. Welsh & Powell (1967)
14. Brèlaz (1979)
15. Cole & Vishkin (1986), see also Cormen, Leiserson & Rivest (1990, Section 30.5)
16. Goldberg, Plotkin & Shannon (1988)
17. Barenboim & Elkin (2009); see also Kuhn (2009)
18. Leith (2006) and Duffy (2008)
19. Dailey (1980)
20. Halldórsson (1993)
21. Zuckerman (2007)
22. Guruswami & Khanna (2000)
23. Khot (2001)
24. Jaeger, Vertigan & Welsh (1990)
25. Goldberg & Jerrum (2008)
26. Holyer (1981)
27. Crescenzi & Kann (1998)
28. Marx (2004)
29. Chaitin (1982)

参考文献

• Barenboim, L.; Elkin, M. (2009), “Distributed (Δ + 1)-coloring in linear (in Δ) time”, Proceedings of the 41st Symposium on Theory of Computing, pp. 111–120, doi:10.1145/1536414.1536432 
• Beigel, R.; Eppstein, D. (2005), “3-coloring in time O(1.3289^n)”, Journal of Algorithms 54 (2)): 168–204, doi:10.1016/j.jalgor.2004.06.008 
• Björklund, A.; Husfeldt, T.; Koivisto, M. (2009), “Set partitioning via inclusion–exclusion”, SIAM Journal on Computing 39 (2): 546–563, doi:10.1137/070683933 
• Brèlaz, D. (1979), “New methods to color the vertices of a graph”, Communications of the ACM 22: 251–256, doi:10.1145/359094.359101 
• Brooks, R. L.; Tutte, W. T. (1941), “On colouring the nodes of a network”, Proceedings of the Cambridge Philosophical Society 37: 194–197, doi:10.1017/S030500410002168X 
• de Bruijn, N. G.; Erdős, P. (1951), “A colour problem for infinite graphs and a problem in the theory of relations”, Nederl. Akad. Wetensch. Proc. Ser. A 54: 371–373, http://www.math-inst.hu/~p_erdos/1951-01.pdf  (= Indag. Math. 13)
• Byskov, J.M. (2004), “Enumerating maximal independent sets with applications to graph colouring”, Operations Research Letters 32: 547–556, doi:10.1016/j.orl.2004.03.002 
• Chaitin, G. J. (1982), “Register allocation & spilling via graph colouring”, Proc. 1982 SIGPLAN Symposium on Compiler Construction, pp. 98–105, doi:10.1145/800230.806984 
• Cole, R.; Vishkin, U. (1986), “Deterministic coin tossing with applications to optimal parallel list ranking”, Information and Control 70 (1): 32–53, doi:10.1016/S0019-9958(86)80023-7 
• Cormen, T. H.; Leiserson, C. E.; Rivest, R. L. (1990), Introduction to Algorithms (1st ed.), The MIT Press 
• Dailey, D. P. (1980), “Uniqueness of colorability and colorability of planar 4-regular graphs are NP-complete”, Discrete Mathematics 30: 289–293, doi:10.1016/0012-365X(80)90236-8 
• Duffy, K.; O'Connell, N.; Sapozhnikov, A. (2008), “Complexity analysis of a decentralised graph colouring algorithm”, Information Processing Letters 107: 60–63, doi:10.1016/j.ipl.2008.01.002 
• Fawcett, B. W. (1978), “On infinite full colourings of graphs”, Canadian Journal of Mathematics XXX: 455–457 
• Garey, M. R.; Johnson, D. S. (1979), Computers and Intractability: A Guide to the Theory of NP-Completeness, W.H. Freeman, ISBN 0-7167-1045-5 
• Garey, M. R.; Johnson, D. S.; Stockmeyer, L. (1974), “Some simplified NP-complete problems”, Proceedings of the Sixth Annual ACM Symposium on Theory of Computing, pp. 47–63, http://portal.acm.org/citation.cfm?id=803884 
• Goldberg, L. A.; Jerrum, M. (July 2008), “Inapproximability of the Tutte polynomial”, Information and Computation 206 (7): 908–929, doi:10.1016/j.ic.2008.04.003 
• Goldberg, A. V.; Plotkin, S. A.; Shannon, G. E. (1988), “Parallel symmetry-breaking in sparse graphs”, SIAM Journal on Discrete Mathematics 1 (4): 434–446, doi:10.1137/0401044 
• Guruswami, V.; Khanna, S. (2000), “On the hardness of 4-coloring a 3-colorable graph”, Proceedings of the 15th Annual IEEE Conference on Computational Complexity, pp. 188–197, doi:10.1109/CCC.2000.856749 
• Halldórsson, M. M. (1993), “A still better performance guarantee for approximate graph coloring”, Information Processing Letters 45: 19–23, doi:10.1016/0020-0190(93)90246-6 
• Holyer, I. (1981), “The NP-completeness of edge-coloring”, SIAM Journal on Computing 10: 718–720, doi:10.1137/0210055 
• Crescenzi, P.; Kann, V. (December 1998), “How to find the best approximation results — a follow-up to Garey and Johnson”, ACM SIGACT News 29: 90, doi:10.1145/306198.306210 
• Jaeger, F.; Vertigan, D. L.; Welsh, D. J. A. (1990), “On the computational complexity of the Jones and Tutte polynomials”, Mathematical Proceedings of the Cambridge Philosophical Society 108: 35–53, doi:10.1017/S0305004100068936 
• Jensen, T. R.; Toft, B. (1995), Graph Coloring Problems, Wiley-Interscience, New York, ISBN 0-471-02865-7 
• Khot, S. (2001), “Improved inapproximability results for MaxClique, chromatic number and approximate graph coloring”, Proc. 42nd Annual Symposium on Foundations of Computer Science, pp. 600–609, doi:10.1109/SFCS.2001.959936 
• Kubale, M. (2004), Graph Colorings, American Mathematical Society, ISBN 0-8218-3458-4 
• Kuhn, F. (2009), “Weak graph colorings: distributed algorithms and applications”, Proceedings of the 21st Symposium on Parallelism in Algorithms and Architectures, pp. 138–144, doi:10.1145/1583991.1584032 
• Lawler, E.L. (1976), “A note on the complexity of the chromatic number problem”, Information Processing Letters 5 (3): 66–67, doi:10.1016/0020-0190(76)90065-X 
• Leith, D.J.; Clifford, P. (2006), “A Self-Managed Distributed Channel Selection Algorithm for WLAN”, Proc. RAWNET 2006, Boston, MA 
• Linial, N. (1992), “Locality in distributed graph algorithms”, SIAM Journal on Computing 21 (1): 193–201, doi:10.1137/0221015 
• van Lint, J. H.; Wilson, R. M. (2001), A Course in Combinatorics (2nd ed.), Cambridge University Press, ISBN 0-521-80340-3 
• Marx, Dániel (2004), “Graph colouring problems and their applications in scheduling”, Periodica Polytechnica, Electrical Engineering, 48, pp. 11–16, http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.95.4268&rep=rep1&type=pdf 
• Mycielski, J. (1955), “Sur le coloriage des graphes”, Colloq. Math. 3: 161–162, http://matwbn.icm.edu.pl/ksiazki/cm/cm3/cm3119.pdf 
• Panconesi, Alessandro; Rizzi, Romeo (2001), “Some simple distributed algorithms for sparse networks”, Distributed Computing (Berlin, New York: Springer-Verlag) 14 (2): 97–100, doi:10.1007/PL00008932, ISSN 0178-2770 
• Sekine, K.; Imai, H.; Tani, S. (1995), “Computing the Tutte polynomial of a graph of moderate size”, Proc. 6th International Symposium on Algorithms and Computation (ISAAC 1995), Lecture Notes in Computer Science, 1004, Springer, pp. 224–233, doi:10.1007/BFb0015427 
• Welsh, D. J. A.; Powell, M. B. (1967), “An upper bound for the chromatic number of a graph and its application to timetabling problems”, The Computer Journal 10 (1): 85–86, doi:10.1093/comjnl/10.1.85 
• West, D. B. (1996), Introduction to Graph Theory, Prentice-Hall, ISBN 0-13-227828-6 
• Wilf, H. S. (1986), Algorithms and Complexity, Prentice–Hall 
• Zuckerman, D. (2007), “Linear degree extractors and the inapproximability of Max Clique and Chromatic Number”, Theory of Computing 3: 103–128, doi:10.4086/toc.2007.v003a006 
• Zykov, A. A. (1949), “О некоторых свойствах линейных комплексов (On some properties of linear complexes)” (Russian), Math. Sbornik. 24(66) (2): 163–188, http://mi.mathnet.ru/eng/msb5974 

関連項目

• 四色定理
• 数独

外部リンク

• Chromatic number of a space at PlanetMath.org
• Graph Coloring Page by Joseph Culberson （グラフ彩色プログラム）
• CoLoRaTiOn by Jim Andrews and Mike Fellows （グラフ彩色パズルゲーム）
• 各種グラフ彩色プログラムのソースへのリンク集
• Code for efficiently computing Tutte, Chromatic and Flow Polynomials by Gary Haggard, David J. Pearce and Gordon Royle