グラフ彩色さいしき

3色しょくに頂点ちょうてん彩色さいしき（最適さいてき彩色さいしき）されたグラフ。ピーターセングラフの彩色さいしき数すうは3である。

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

概要がいよう

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

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

グラフ彩色さいしきはグラフのラベル付らべるつけとは異ことなる。ラベル付らべるつけは数かずで表あらわされる「ラベル」を頂点ちょうてんや辺あたりに割わり当あてるものである。グラフ彩色さいしき問題もんだいでは、色いろ（を表あらわす数かず）は任意にんいのマーカーであり、隣接りんせつ性せいや結合けつごう性せいに関かかわる状態じょうたいを表あらわす。グラフのラベル付らべるつけ問題もんだいでは、ラベル（を表あらわす数かず）は計算けいさん可能かのうな値ねであり、ラベル付らべるつけの際さいの定義ていぎで示しめされる何なんらかの数値すうち的てき条件じょうけんを満みたす必要ひつようがある。

グラフ彩色さいしき問題もんだいは理論りろん的てきにも意味いみがあるが、実用じつよう的てきな応用おうようも多おおい。古典こてん的てき問題もんだい以外いがいにも、色いろの割わり当あて方かたや色いろ自体じたいに異ことなる制約せいやくを加くわえた問題もんだいもある。広ひろく知しられているパズルである数かず独どくもグラフ彩色さいしき問題もんだいの変形へんけいである。グラフ彩色さいしきは研究けんきゅうが盛さかんな分野ぶんやのひとつである。

歴史れきし

「四よん色しょく定理ていり#歴史れきし」も参照さんしょう

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

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

1912年ねん、彩色さいしき問題もんだいを研究けんきゅうする過程かていでジョージ・デビット・バーコフが彩色さいしき多項式たこうしきを導入どうにゅう。これをW・T・タットがタット多項式たこうしきとして一般いっぱん化かし、代数だいすう的てきグラフ理論りろんの重要じゅうような構成こうせい要素ようそとなっている。ケンプは1879年ねんの時点じてんで既すでに平面へいめんグラフ以外いがいのグラフ一般いっぱんにも言及げんきゅうしており、グラフ彩色さいしきのより高次こうじのグラフへの一般いっぱん化かは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 個この頂点ちょうてんからなる完全かんぜんグラフ（あらゆる頂点ちょうてん間あいだに辺あたりがあるグラフ）$K_{n}$ の彩色さいしき数すうは、$\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	…

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

彩色さいしき多項式たこうしきは彩色さいしき数すうと共ともに、$G$ の彩色さいしき可能かのう性せいについての情報じょうほうをもたらす。実際じっさい、彩色さいしき数すう χかい は彩色さいしき多項式たこうしきの根ねではない最小さいしょうの正せいの整数せいすうである。

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

この概念がいねんを最初さいしょに使つかったのは George David Birkhoff と D. C. Lewis であり、四よん色しょく定理ていりの証明しょうめいを試こころみる過程かていで用もちいた。

特定とくていのグラフに関かんする彩色さいしき多項式たこうしき

三角形さんかっけい $K_{3}$	$t(t-1)(t-2)$
完全かんぜんグラフ $K_{n}$	$t(t-1)(t-2)$...$(t-(n-1))$
$n$ 頂点ちょうてんの木き	$t(t-1)^{n-1}$
閉路へいろグラフ $C_{n}$	$(t-1)^{n}+(-1)^{n}(t-1)$
ピーターセングラフ	$t(t-1)(t-2)(t^{7}-12t^{6}+67t^{5}-230t^{4}+529t^{3}-814t^{2}+775t-352)$

彩色さいしき多項式たこうしきには次つぎのような属性ぞくせいがある。

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

辺あたり彩色さいしき

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

属性ぞくせい

彩色さいしき数すうの境界きょうかい

個々ここの頂点ちょうてんにそれぞれ異ことなる色いろを割わり当あてれば、その彩色さいしきは正ただしい。従したがって次つぎが成なり立たつ。

$1\leq \chi (G)\leq n\,$

1-彩色さいしき可能かのうなのは辺あたりのないグラフに限かぎられる。n個この頂点ちょうてんを持もつ完全かんぜんグラフ $K_{n}$ を彩色さいしきするには $\chi (K_{n})=n$ 色いろが必要ひつようである。最適さいてきな彩色さいしきでは、グラフ内ないの m 個こ以上いじょうの辺あたりが色いろクラス間あいだを結むすぶ位置いちにある。従したがって、次つぎが成なり立たつ。

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

G に大おおきさ k のクリークが含ふくまれている場合ばあい、そのクリークの彩色さいしきに少すくなくとも k 色いろを必要ひつようとする。い換いかえれば、グラフ G の彩色さいしき数すうについて次つぎが成なり立たつ。

$\chi (G)\geq \omega (G)\,$

区間くかんグラフでは、この境界きょうかいがきつい。

2-彩色さいしき可能かのうなグラフは常つねに2部ぶグラフであり、木きや森もりもそれに含ふくまれる。四よん色しょく定理ていりにより、全すべての平面へいめんグラフは4-彩色さいしき可能かのうである。

貪欲どんよく彩色さいしき法ほうによれば、あらゆるグラフは頂点ちょうてんの最大さいだい次数じすうより1つ多おおい色いろ数すうで彩色さいしき可能かのうである。

$\chi (G)\leq \Delta (G)+1\,$

完全かんぜんグラフは $\chi (G)=n$ かつ $\Delta (G)=n-1$ であり、奇き閉路へいろは $\chi (G)=3$ かつ $\Delta (G)=2$ である。したがってこの境界きょうかい条件じょうけんはこれらのグラフでは彩色さいしき数すうをよく限定げんていする。それら以外いがいのグラフでは、境界きょうかい条件じょうけんをさらに若干じゃっかん改良かいりょうする余地よちがある。ブルックスの定理ていりは次つぎの通とおりである。

ブルックスの定理ていり: 完全かんぜんグラフでも奇き閉路へいろでもない単純たんじゅんな連結れんけつグラフ G について $\chi (G)\leq \Delta (G)$ が成なり立たつ。

彩色さいしき数すうの大おおきいグラフ

最大さいだいクリークの大おおきなグラフは彩色さいしき数すうも大おおきいが、逆ぎゃくは必かならずしも真しんではない。Grötzschグラフ(en)は4-彩色さいしき的てきだが、三角形さんかっけいを含ふくまない（クリークがない）。それを一般いっぱん化かしたグラフをMycielskianと呼よぶ。

Mycielskiの定理ていり: 三角形さんかっけいを含ふくまない、任意にんいの彩色さいしき数すうのグラフが存在そんざいする。

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

定理ていり（エルデシュ）: 任意にんいの内うち周しゅうが大おおきくかつ彩色さいしき数すうの大おおきいグラフが存在そんざいする。

彩色さいしき指数しすうの境界きょうかい

G の辺あたり彩色さいしきは、そのライングラフ $L(G)$ の頂点ちょうてん彩色さいしきと等価とうかであり、逆ぎゃくも成なり立たつ。従したがって、

$\chi '(G)=\chi (L(G))\,$

辺あたり彩色さいしき可能かのう性せいとそのグラフの最大さいだい次数じすう $\Delta (G)$ には強つよい関連かんれん性せいがある。同おなじ頂点ちょうてんに接合せつごうする全すべての辺あたりは異ことなる色いろにしなければならないので、次つぎが成なり立たつ。

$\chi '(G)\geq \Delta (G)\,$

さらに次つぎが成なり立たつ。

ケーニグの定理ていり: G が2部ぶグラフなら $\chi '(G)=\Delta (G)$

一般いっぱんに、この関係かんけいはブルックスの定理ていりが頂点ちょうてん彩色さいしきに与あたえる関係かんけいよりも強つよい。

Vizingの定理ていり: 最大さいだい次数じすう $\Delta$ のグラフの辺あたり彩色さいしき数すうは $\Delta$ または $\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のいずれかだということまでは判明はんめいしている。その他たのグラフの彩色さいしき数すうに関かんする未み解決かいけつ問題もんだいとしては、Hadwiger予想よそう(en)がある。これは、彩色さいしき数すう k のグラフはマイナーとして頂点ちょうてん k 個この完全かんぜんグラフを含ふくむ、という予想よそうである。また、Erdős–Faber–Lovász予想よそう(en)は、k-クリークが互たがいに高々たかだか1つの頂点ちょうてんを共有きょうゆうする形かたちでk個こ連結れんけつされたグラフはk-彩色さいしき的てきだ、というものである。Albertson予想よそう(en)は、k-彩色さいしき的てきグラフの中なかで完全かんぜんグラフが最もっとも交差こうさ数すうが小ちいさい、というものである。

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

アルゴリズム

グラフ彩色さいしき
決定けってい問題もんだい
名称めいしょう	グラフ彩色さいしき、頂点ちょうてん彩色さいしき、k-彩色さいしき
入力にゅうりょく	n 個この頂点ちょうてんを持もつグラフ G。整数せいすう k
出力しゅつりょく	G は k 個この色いろで最適さいてき彩色さいしき可能かのうか?
時間じかん計算けいさん量りょう	O(2 nn)
複雑ふくざつ性せいクラス	NP完全かんぜん
還元かんげん	3-SAT
Garey–Johnson	GT4
最適さいてき化か問題もんだい
名称めいしょう	彩色さいしき数すう
入力にゅうりょく	n 個この頂点ちょうてんを持もつグラフ G
出力しゅつりょく	χかい(G)
複雑ふくざつ性せいクラス	NP困難こんなん
近似きんじ計算けいさん量りょう	O(n (log n)−3(log log n)2)
非ひ近似きんじ計算けいさん量りょう	O(n1−εいぷしろん) - P=NPでない場合ばあい
数かぞえ上あげ問題もんだい
名称めいしょう	彩色さいしき多項式たこうしき
入力にゅうりょく	n 個この頂点ちょうてんを持もつグラフ G。整数せいすう k
出力しゅつりょく	G を k-彩色さいしきする場合ばあいの P (G,k) の値ね
時間じかん計算けいさん量りょう	O(2 nn)
複雑ふくざつ性せいクラス	#P完全かんぜん
近似きんじ計算けいさん量りょう	多項式たこうしき時間じかん - 一部いちぶのケースのみ
非ひ近似きんじ計算けいさん量りょう	P=NPでない場合ばあい、多項式たこうしき時間じかんアルゴリズムは存在そんざいしない。

多項式たこうしき時間じかん

あるグラフが2色しょくで彩色さいしき可能かのうかどうかを決定けっていする問題もんだいは、そのグラフが2部ぶグラフかどうかの決定けってい問題もんだいと等価とうかであり、幅優先はばゆうせん探索たんさくを使つかって多項式たこうしき時間じかんで解とける。より一般いっぱん化かすれば、パーフェクトグラフの彩色さいしき数すうと具体ぐたい的てきな彩色さいしきは半はん正せい定値ていち計画けいかく法ほうを使つかって多項式たこうしき時間じかんで計算けいさんできる。森もり、弦つるグラフ、閉路へいろグラフ、車輪しゃりんグラフ、梯子はしごグラフといった種類しゅるいのグラフは彩色さいしき多項式たこうしきがわかっているので、多項式たこうしき時間じかんでの評価ひょうかが可能かのうである。

正確せいかくなアルゴリズム

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

動的どうてき計画けいかく法ほうと最大さいだい独立どくりつ集合しゅうごうの数かずの制約せいやくを利用りようするとk-彩色さいしき可能かのう性せいの判定はんていは時間じかんおよび空間くうかん計算けいさん量りょう $O(2.445^{n})$ で行おこなえる。包つつみ除じょ原理げんりと高速こうそくゼータ変換へんかんのためのYatesのアルゴリズムを使つかえば、k-彩色さいしき可能かのう性せいの判定はんていは任意にんいのkについて $O(2^{n}n)$ の時間じかんで行おこなえる。3-彩色さいしき可能かのう性せいおよび4-彩色さいしき可能かのう性せいの判定はんていについてはさらに高速こうそくなアルゴリズムが知しられており、それぞれ $O(1.3289^{n})$ および $O(1.7504^{n})$ の時間じかんで判定はんていできる。

縮ちぢみ約やく

グラフ G の縮ちぢみ約やく $G/uv$ とは、グラフ内ないの頂点ちょうてん u と v を特定とくていし、それらの間あいだの辺あたりを全すべて除去じょきょし、その2つの頂点ちょうてんを1つの新あらたな頂点ちょうてん w に置おき換かえ、u や v と接合はぎあわしていた全すべての辺あたりを w に繋つなぎかえることでできるグラフである。この操作そうさはグラフ彩色さいしきの解析かいせきにおいて重要じゅうような役割やくわりを演えんじる。

Zykov (1949) によれば、彩色さいしき数すうは次つぎの漸やや化か式しきを満みたす。

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

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

彩色さいしき多項式たこうしきは次つぎの漸すすむ化か式しきを満みたす。

$P(G-uv,k)=P(G/uv,k)+P(G,k)$

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

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

貪欲どんよく彩色さいしき

同おなじグラフにおいて2種類しゅるいの頂点ちょうてんの順序じゅんじょ付づけをしたときの貪欲どんよく彩色さいしき。うまく順序付じゅんじょづけすれば2-彩色さいしき可能かのうだが、貪欲どんよく彩色さいしきでは $n/2$ 色いろまで費ついやすことがある。

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

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

並列へいれつアルゴリズムと分散ぶんさんアルゴリズム

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

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

単純たんじゅんで興味深きょうみぶかい例れいとして n-閉路へいろグラフがある。Richard Cole と Uzi Vishkinによれば、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) となる。(Δでるた + 1)-彩色さいしきの既知きちの最さい高速こうそくアルゴリズムとしては、Leonid Barenboim と Michael Elkin のものがある。その計算けいさん時間じかんは O(Δでるた) + log*(n)/2 であり、Linialの下限かげんによれば 1/2 という係数けいすうはこれ以上いじょう改善かいぜんできないので n に対たいして最適さいてきなアルゴリズムということになる。

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

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

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

計算けいさん量りょう

グラフ彩色さいしきは困難こんなんである。k = 1 および k = 2 以外いがいの k について「与あたえられたグラフがk-彩色さいしき可能かのうか」という決定けってい問題もんだいはNP完全かんぜん問題もんだいである。彩色さいしき数すうを求もとめる問題もんだいはNP困難こんなんである。彩色さいしき可能かのう性せいを問とう決定けってい問題もんだいは次数じすうが最大さいだい4の平面へいめんグラフであってもNP完全かんぜんである。

既知きちの最良さいりょうの近似きんじアルゴリズムはオーダー O(n(log n)⁻³(log log n)²) の近似きんじ精度せいどで彩色さいしき数すうを計算けいさんする。あらゆる εいぷしろん > 0 について、n^{1−εいぷしろん} 以内いないに彩色さいしき数すうを近似きんじすることはNP困難こんなんである。

3-彩色さいしき可能かのうなグラフを4色しょくで彩色さいしきする問題もんだいもNP困難こんなんであり、k-彩色さいしき可能かのうなグラフを k^{(log k ) / 25} 色いろで彩色さいしきする問題もんだいも k が十分じゅうぶん大おおきければNP困難こんなんである。

彩色さいしき多項式たこうしきの係数けいすうを求もとめる問題もんだいは#P困難こんなんである。実際じっさい k = 1 または k = 2 以外いがいの任意にんいの有理数ゆうりすう k について $\chi (G,k)$ を求もとめる計算けいさんも#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-彩色さいしき問題もんだいとみなすことができる。

参考さんこう文献ぶんけん

• 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ⁿ)”, 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