グラフ彩色（英: Graph coloring）とは、グラフの何らかの要素に、ある制約条件を満たすように色を割り当てることである。最も単純なものは、隣接する頂点同士が同じ色にならないように全頂点に彩色する問題である。これを頂点彩色という。同様に辺彩色は、隣接する辺同士が同じ色にならないように全辺を彩色する問題、面彩色は、平面グラフの辺で囲まれた各領域（面）を隣接する面同士が同じ色にならないように彩色する問題である。頂点彩色が出発点であり、他の彩色問題は頂点彩色に変換可能である。例えば、辺彩色問題は、そのグラフをライングラフに変換したときの頂点彩色と同じであり、面彩色は平面グラフの双対グラフの頂点彩色と同じである。しかし、頂点彩色以外の問題もそのままの形で研究されている。これは、見通しの良さのためでもあり、頂点彩色以外の形式で研究が進んでいるためでもある。彩色という表現を使うようになったのは、地図を国ごとに彩色する問題が起源である。地図の彩色問題は、平面グラフの面彩色問題に他ならない。また平面グラフの双対性により、頂点彩色問題とも等価であり、あらゆるグラフの問題として一般化できる。数学やコンピュータでは、非負または正の小さい整数を「色」を表現する値として使うことが多い。一般に、任意の有限集合を「色集合」として使うことができる。彩色問題の性質は色数には依存するが、個々の色をどう表すかは関係しない。グラフ彩色はグラフのラベル付けとは異なる。ラベル付けは数で表される「ラベル」を頂点や辺に割り当てるものである。グラフ彩色問題では、色（を表す数）は任意のマーカーであり、隣接性や結合性に関わる状態を表す。グラフのラベル付け問題では、ラベル（を表す数）は計算可能な値であり、ラベル付けの際の定義で示される何らかの数値的条件を満たす必要がある。グラフ彩色問題は理論的にも意味があるが、実用的な応用も多い。古典的問題以外にも、色の割り当て方や色自体に異なる制約を加えた問題もある。広く知られているパズルである数独もグラフ彩色問題の変形である。グラフ彩色は研究が盛んな分野のひとつである。グラフ彩色は、地図の色分けの形で始まったものであり、当初はほとんど平面グラフだけを対象としていた。イングランドの地図をカウンティごとに色分けしようとしたフランシス・ガスリーは、4色あればどの境界線も両側が同じ色になることがないよう色分けできることに気づき、四色定理を主張した。ガスリーの兄弟がこの問題を数学の先生だったユニヴァーシティ・カレッジ・ロンドンのオーガスタス・ド・モルガンに提示してみたところ、彼は1852年にウィリアム・ローワン・ハミルトンへの手紙でこの問題に言及した。1879年、ロンドン数学会の会合でアーサー・ケイリーがこの問題を提示した。同年、アルフレッド・ケンプがその証明をしたとする論文を発表し、その後10年ほどはこの問題は証明済みとみなされていた。この業績によってケンプは王立協会フェローに選ばれ、後にロンドン数学会の会長に就任している。1890年、パーシー・ヘイウッドはケンプの証明が間違っていることを指摘した。ケンプの証明は地図の塗りわけに「五色」あれば十分であることを示したに過ぎなかった。その後約1世紀に渡って四色定理を証明すべく様々な努力がなされ、とうとう1976年にケネス・アッペルとヴォルフガング・ハーケンが証明した。驚くべきことに、その証明の考え方はヘイウッドやケンプの考え方に沿ったもので、途中の数十年間の様々な努力は無視されている。四色定理の証明では初めて大規模にコンピュータを利用したことも注目に値する。1912年、彩色問題を研究する過程でジョージ・デビット・バーコフが彩色多項式を導入。これをW・T・タットがタット多項式として一般化し、代数的グラフ理論の重要な構成要素となっている。ケンプは1879年の時点で既に平面グラフ以外のグラフ一般にも言及しており、グラフ彩色のより高次のグラフへの一般化は20世紀初頭から続々となされていった。1960年、クロード・ベルジュはグラフ彩色についての新たな予想である「強パーフェクトグラフ予想」を定式化した。これは、クロード・シャノンの情報理論の概念であるグラフのゼロエラー容量が発想の元になっている。この予想は40年間証明されなかったが、2002年に、、、が証明し、「強パーフェクトグラフ定理」となった。1970年ごろから、グラフ彩色についてのアルゴリズムの研究が盛んになってきた。彩色数問題は1972年にリチャード・カープが提案した21のNP完全問題の1つになっており、ほぼ同じころにバックトラッキングや の削除・縮約の繰り返し (deletion-contraction recurrence) などに基づいた指数関数時間の様々なアルゴリズムが開発された。グラフ彩色の応用の1つとしてコンパイラにおけるレジスタ割り付けがあり、1981年に登場した。単にグラフの彩色(coloring)と言った場合、「頂点彩色」を意味することが多い。また、隣接する頂点が同じ色にならないよう彩色すること、すなわち最適彩色を意味する。隣接する頂点とは、同じ辺と接している頂点である。ある頂点から同じ頂点へ戻る辺（ループ）が存在する場合、頂点彩色問題は決して最適解を持たないので、以下ではループがないグラフのみを扱う。頂点のラベルを「色」で表すのは地図の塗りわけに起源がある。「赤」や「青」といったラベルは色数が小さい場合のみ使われ、一般にはラベルとして整数 {1,2,3...} を使う。最大 "k" 色を使った彩色を k"-彩色と言う。グラフ "G" の彩色に必要な最小の色数を彩色数(chromatic number)と呼び χ("G") で表す。例えば、"n" 個の頂点からなる完全グラフ（あらゆる頂点間に辺があるグラフ）formula_1 の彩色数は、formula_2 である。"k"-彩色できるグラフをk"-彩色可能("k"-colorable)といい、その"k"がそのグラフの彩色数であるとき、"k"-彩色的("k"-chromatic)という。同じ色が割り当てられた頂点の部分集合を「色クラス」と呼び、色クラス同士は独立集合となっている。したがって、"k"-彩色することは、頂点集合を "k" 個の独立部分集合に分割するのと等価であり、"k"-部 ("k"-partite) グラフや "k"-彩色可能といった用語も同じ意味を持つ。彩色多項式(chromatic polynomial)とは、与えられたグラフを与えられた色数内で彩色したときの彩色の組合せ数を求める式である。例えば、右図のグラフは3色で彩色すると12通りの彩色が可能である。2色では彩色できない。4色では 24 + 4×12 = 72 通りである。4色を使った彩色は24通りで、4色のうちの3色を使った彩色はそれぞれ12通りなので、このような計算になる（4色を4つの頂点に割り当てる場合は、任意の組み合わせが可能である）。従って、このグラフの彩色数を表にすると次のようになる。彩色多項式は、formula_3 で表され、グラフ formula_4 を formula_5 色で彩色したときの色の組合せ数である。名前が示すとおり、ある formula_4 についての彩色多項式は、formula_5 に関する多項式となる。例に挙げたグラフでは、formula_8 となる。彩色多項式は彩色数と共に、formula_4 の彩色可能性についての情報をもたらす。実際、彩色数 χ は彩色多項式の根ではない最小の正の整数である。この概念を最初に使ったのは George David Birkhoff と D. C. Lewis であり、四色定理の証明を試みる過程で用いた。彩色多項式には次のような属性がある。グラフの辺彩色とは、グラフの辺を彩色するもので、1つの頂点に接合するそれぞれの辺が常に別々の色になるように最適彩色する。"k"色を使った辺彩色を「"k"-辺彩色」と呼び、辺集合を"k"個のマッチングに分割する問題と等価である。グラフ "G" の辺彩色に必要な最小の色数を彩色指数 (chromatic index) または辺彩色数 (edge chromatic number) と呼び、"χ′(G)" で表す。テイト彩色 (Tait coloring) とは、立方体グラフ（3-正則グラフ）の3-辺彩色を意味する。四色定理は、3-正則で辺が交差しない平面グラフをテイト彩色できることと等価である。個々の頂点にそれぞれ異なる色を割り当てれば、その彩色は正しい。従って次が成り立つ。1-彩色可能なのは辺のないグラフに限られる。"n"個の頂点を持つ完全グラフ formula_1 を彩色するには formula_2 色が必要である。最適な彩色では、グラフ内の "m" 個以上の辺が色クラス間を結ぶ位置にある。従って、次が成り立つ。"G" に大きさ "k" のクリークが含まれている場合、そのクリークの彩色に少なくとも "k" 色を必要とする。言い換えれば、グラフ "G" の彩色数について次が成り立つ。インターバルグラフでは、この境界がきつい。2-彩色可能なグラフは常に2部グラフであり、木や森もそれに含まれる。四色定理により、全ての平面グラフは4-彩色可能である。貪欲彩色法によれば、あらゆるグラフは頂点の最大次数より1つ多い色数で彩色可能である。完全グラフは formula_44 かつ formula_45 であり、奇閉路は formula_46 かつ formula_47 である。したがってこの境界条件はこれらのグラフでは彩色数をよく限定する。それら以外のグラフでは、境界条件をさらに若干改良する余地がある。ブルックスの定理は次の通りである。最大クリークの大きなグラフは彩色数も大きいが、逆は必ずしも真ではない。Grötzschグラフ()は4-彩色的だが、三角形を含まない（クリークがない）。それを一般化したグラフをと呼ぶ。ブルックスの定理から、彩色数の大きいグラフは次数が高くなければならない。また、局所的には大きなクリークがあれば彩色数は大きくなる。しかし、彩色可能性はグラフの局所的現象ではない。内周（最短閉路の長さ）が大きいグラフは、局所的に見れば木のようになっているが、その彩色数は2になるとは限らない。"G" の辺彩色は、そのライングラフ formula_49 の頂点彩色と等価であり、逆も成り立つ。従って、辺彩色可能性とそのグラフの最大次数 formula_51 には強い関連性がある。同じ頂点に接合する全ての辺は異なる色にしなければならないので、次が成り立つ。さらに次が成り立つ。一般に、この関係はブルックスの定理が頂点彩色に与える関係よりも強い。平面グラフでは、頂点彩色は基本的に と双対関係にある。無限グラフについては、まだよく判っていない。無限グラフの彩色について判明している数少ない事実として次の事柄がある。単位距離だけ離れている任意の2つの点が同じ色にならないように平面を彩色する問題 () は未解決だが、その彩色数は4、5、6、7のいずれかだということまでは判明している。その他のグラフの彩色数に関する未解決問題としては、Hadwiger予想()がある。これは、彩色数 "k" のグラフはマイナーとして頂点 "k" 個の完全グラフを含む、という予想である。また、Erdős–Faber–Lovász予想()は、"k"-クリークが互いに高々1つの頂点を共有する形で"k"個連結されたグラフは"k"-彩色的だ、というものである。Albertson予想()は、"k"-彩色的グラフの中で完全グラフが最も交差数が小さい、というものである。BirkhoffとLewisは四色問題を攻略する手段として彩色多項式を導入し、平面グラフ "G" の彩色多項式 formula_3 は formula_58 の領域でゼロにならないという予想を立てた。そのような彩色多項式が formula_59 の領域でゼロにならないことと、formula_60 であることは判明しているが、彼らの予想自体は未解決である。任意の2つのグラフの彩色多項式が同一かどうかの判定や、ある多項式が彩色多項式かどうかの判定も未解決の問題である。あるグラフが2色で彩色可能かどうかを決定する問題は、そのグラフが2部グラフかどうかの決定問題と等価であり、幅優先探索を使って多項式時間で解ける。より一般化すれば、パーフェクトグラフの彩色数と具体的な彩色は半正定値計画法を使って多項式時間で計算できる。森、弦グラフ、閉路グラフ、車輪グラフ、梯子グラフといった種類のグラフは彩色多項式がわかっているので、多項式時間での評価が可能である。"k"-彩色の判定を力まかせ探索で行う場合、"n" 個の頂点に "k" 色を割り当てる formula_61 の組み合わせを全て試し、制約をみたしているか調べる。彩色数や彩色多項式を計算する場合、力まかせ探索では formula_62 の全ての "k" について同じ作業をすることになり、小さいグラフ以外では現実的でない。動的計画法と最大独立集合の数の制約を利用すると"k"-彩色可能性の判定は時間および空間計算量 formula_63 で行える。包除原理と高速ゼータ変換のためののアルゴリズムを使えば、"k"-彩色可能性の判定は任意の"k"について formula_64 の時間で行える。3-彩色可能性および4-彩色可能性の判定についてはさらに高速なアルゴリズムが知られており、それぞれ formula_65 および formula_66 の時間で判定できる。グラフ "G" の縮約 formula_67 とは、グラフ内の頂点 "u" と "v" を特定し、それらの間の辺を全て除去し、その2つの頂点を1つの新たな頂点 "w" に置き換え、"u" や "v" と接合していた全ての辺を "w" に繋ぎかえることでできるグラフである。この操作はグラフ彩色の解析において重要な役割を演じる。"u" と "v" が隣接した頂点でない場合、formula_69 は辺 formula_70 を加えたグラフを意味する。この漸化式を評価することに基づくアルゴリズムもいくつかあり、それによって形成される計算木を Zykov 木と呼ぶこともある。実際にかかる時間は頂点 "u" と "v" の選択のしかた（ヒューリスティック）に依存する。彩色多項式は次の漸化式を満たす。"u" と "v" が隣接した頂点の場合、formula_72 は辺 formula_70 を除去したグラフを意味する。formula_74 はそのグラフの彩色の組み合わせ数を表し、"u" と "v" が同色の場合もそうでない場合も含まれる。上の式から、彩色の組み合わせ数は2つのグラフの彩色組み合わせ数の和で表される。頂点 "u" と "v" の色が異なる場合、"u" と "v" が1つの辺で結ばれたグラフでも同じ彩色が可能である。"u" と "v" が同色の場合、"u" と "v" を縮約したグラフと同じとみなすことができる。W・T・タットはこの漸化式を満たすグラフの属性について興味を持ち、彩色多項式を一般化したタット多項式を発見した。これらから、再帰的な手続きが考えられ、それを削除・縮約アルゴリズム (deletion–contraction algorithm) と呼び、多くのグラフ彩色アルゴリズムの基盤となっている。すなわち、与えられたグラフを辺が1つ少ない2つのグラフに変換し、それを再帰的に繰り返すのである。これはフィボナッチ数と同様の再帰属性を持ち、最悪でも formula_75 の処理時間となる。さらに入力されたグラフのスパニング木の数 formula_76 の多項式の係数を応用することで解析を改善することができる。実際には、分枝限定法を使い、同型のグラフを排除することで再帰回数を減らすことができ、処理時間は2つの頂点を選ぶ際のヒューリスティックに依存する。貪欲法では、頂点に所定の順序 formula_77,…,formula_78 を設定し、formula_79 に対して formula_77,…,formula_81 までの隣接する頂点で使っていない色を設定し、それまでに使ったどの色の頂点とも隣接している場合は、新たな色を設定する。結果は頂点をどう順序付けするかに依存し、彩色数 formula_82 による最適彩色を導き出す順序付けも存在することがある。しかし、順序付けによってはもっと悪い結果になる。例えば頂点が "n" 個の は2-彩色的だが、貪欲彩色では formula_83 色を必要とすることがある。頂点を次数が小さくなる順序でソートすれば、貪欲彩色で使う最大色数は formula_84 となり、最悪でもそのグラフの最大次数より1つだけ大きい色数になる。このヒューリスティックを Welsh–Powell アルゴリズムとも呼ぶ。他にも、アルゴリズム実行中に動的に頂点の順序を決定していくヒューリスティックもあり、最も多くの異なる色と隣接している頂点を次の頂点として選ぶという方法もある。他にも様々なヒューリスティクスを採用したアルゴリズムがあり、これらを総称して逐次彩色 (sequential coloring) アルゴリズムと呼ぶこともある。グラフ彩色の分散アルゴリズムは、グラフの「対称性の破れ」の問題と密接に関連する。対称グラフでは、決定的分散アルゴリズムでは最適彩色を見つけることができない。対称性の破れを見つけるには何らかの予備的情報を必要とする。一般的な前提条件として、"n" 個の各頂点に {1, 2, ..., "n"} の一意の識別子を付与した状態、つまりそれぞれが別々の色に彩色された状態を初期状態とする。したがって、なすべきことは "n" 色を例えば Δ + 1 色にまで減らしていくことである。貪欲法を単純に分散アルゴリズム化して(Δ + 1)-彩色を求めるアルゴリズムは、最悪の場合 Θ("n") 回の通信を必要とし、情報をネットワークの一端から全体に伝播させる必要があることもある。ただし、最大次数 Δ が小さければ、もっと高速なアルゴリズムも存在する。単純で興味深い例として "n"-閉路グラフがある。Richard Cole と によれば、1回の同期通信ステップで色数を "n" から "O"(log "n") に減らす分散アルゴリズムが存在する。これを繰り返すと"n"-閉路グラフの3-彩色を "O"(log* "n") の通信ステップで得ることができる（各頂点には一意の識別子が付与されていることが前提）。反復対数関数 log* は成長が非常にゆっくりとしていて、ほぼ定数とみなせる。そこで Cole と Vishkin の成果から、"n"-閉路の3-彩色を求める定数時間の分散アルゴリズムはあるのかという問題が提起される。 によれば、そのようなアルゴリズムは存在しない。決定的分散アルゴリズムは"n"-閉路を"n"-彩色から3-彩色に減らすのに Ω(log* "n")の通信ステップを必要とする。ColeとVishkinの技法は任意の次数の制限されたグラフに適用可能である。その場合の計算時間は poly(Δ) + "O"(log* "n") となる。(Δ + 1)-彩色の既知の最高速アルゴリズムとしては、Leonid Barenboim と Michael Elkin のものがある。その計算時間は "O"(Δ) + log*("n")/2 であり、Linialの下限によれば 1/2 という係数はこれ以上改善できないので "n" に対して最適なアルゴリズムということになる。辺彩色の分散アルゴリズムも研究されてきた。 では、(2Δ − 1)-辺彩色を "O"(Δ + log* "n") の時間で可能なアルゴリズムが示されている。 による分散頂点彩色の下限は、辺彩色問題についても同様に成り立つ。メッセージのやり取りをしない分散アルゴリズム (decentralized algorithm) もある。最適彩色が存在するグラフについて、効率的にそれを求めるアルゴリズムが存在する。この場合、各頂点は隣接する頂点が自分と同じ色かどうかをメッセージをやり取りせずに確認できることを前提とする。例えば無線のチャンネル割り当てなどでは、他の通信機が同じチャンネルを使っているかどうかは容易に検出可能なので、この前提は穏当である。そのような情報があれば、学習するオートマトンが確実なグラフ彩色を見出すのに十分である。グラフ彩色は困難である。"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" について formula_85 を求める計算も#P困難である。NP = RP でない限り、"k" = 2 以外の "k" ≥ 1.5 の有理数 "k" について彩色多項式を評価する多項式時間の近似アルゴリズムは存在しない。辺彩色については、Vizingの証明の結果から最大 Δ+1 色で彩色するアルゴリズムが得られている。しかし、2つの候補値から辺彩色数を決定する問題はNP完全である。近似アルゴリズムの場合、Vizingの辺彩色数を求めるアルゴリズムの近似度は4/3であり、任意の "ε > 0" について(4/3 − "ε" )-近似アルゴリズムは存在しない（P=NPでない限り）。これらは近似アルゴリズムについての最も古い論文である（近似度という記法は明確には使っていない）。頂点彩色は各種スケジューリング問題のモデルとなる。最も単純化したスケジューリング問題は、一連の仕事を時間割にひとつずつ（ある時間には1つの仕事だけをするように）あてはめていくものである。個々の仕事にはリソースの競合など同時に実施できない制約条件がある。これをグラフで表すと、個々の仕事が頂点、競合する仕事を結ぶ線が辺となる。このグラフの彩色数を求める問題は、全部の仕事が終わるまでにかかる時間を最小にすることと等価である。スケジューリング問題の詳細がそのグラフの構造を定義する。例えば航空機の運航スケジューリングの場合、インターバルグラフで表せば効率的に彩色問題として解ける。無線局の帯域幅割り当ての場合、単位円グラフで表せばよい。コンピュータプログラムのコンパイラは、あるプログラミング言語から別の言語への翻訳を行う。その結果生成されるコードの実効効率を向上させるため、レジスタ割り付けというコンパイラ最適化技法が使われる。これは、プログラムで頻繁に使う値を高速なレジスタに保持し続けるようにするものである。理想的には演算に使用する値が常にレジスタに存在することが望ましい。典型的な技法として、この問題をグラフ彩色問題にモデル化する。コンパイラは頂点をレジスタ（変数）とし、辺を同時に必要とされるレジスタ同士を結ぶように配した干渉グラフを構築する。このグラフが"k"色で彩色可能なら、"k"個のレジスタに割り付け可能である。グラフ彩色問題は、パターンマッチなど様々な応用が見つかっている。数独というパズルも、81個の頂点を持つグラフの9-彩色問題とみなすことができる。

出典:wikipedia