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 個 こ の頂点 ちょうてん からなる完全 かんぜん グラフ (あらゆる頂点 ちょうてん 間 あいだ に辺 あたり があるグラフ)
K
n
{\displaystyle K_{n}}
の彩色 さいしき 数 すう は、
χ かい
(
K
n
)
=
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
…
彩色 さいしき 多項式 たこうしき は、
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}
の彩色 さいしき 可能 かのう 性 せい についての情報 じょうほう をもたらす。実際 じっさい 、彩色 さいしき 数 すう χ かい は彩色 さいしき 多項式 たこうしき の根 ね ではない最小 さいしょう の正 せい の整数 せいすう である。
χ かい
(
G
)
=
min
{
k
:
P
(
G
,
k
)
>
0
}
{\displaystyle \chi (G)=\min\{k\colon P(G,k)>0\}}
この概念 がいねん を最初 さいしょ に使 つか ったのは George David Birkhoff と D. C. Lewis であり、四 よん 色 しょく 定理 ていり の証明 しょうめい を試 こころ みる過程 かてい で用 もち いた。
特定 とくてい のグラフに関 かん する彩色 さいしき 多項式 たこうしき
三角形 さんかっけい
K
3
{\displaystyle K_{3}}
t
(
t
−
1
)
(
t
−
2
)
{\displaystyle t(t-1)(t-2)}
完全 かんぜん グラフ
K
n
{\displaystyle K_{n}}
t
(
t
−
1
)
(
t
−
2
)
{\displaystyle t(t-1)(t-2)}
...
(
t
−
(
n
−
1
)
)
{\displaystyle (t-(n-1))}
n
{\displaystyle n}
頂点 ちょうてん の木 き
t
(
t
−
1
)
n
−
1
{\displaystyle t(t-1)^{n-1}}
閉路 へいろ グラフ
C
n
{\displaystyle C_{n}}
(
t
−
1
)
n
+
(
−
1
)
n
(
t
−
1
)
{\displaystyle (t-1)^{n}+(-1)^{n}(t-1)}
ピーターセングラフ
t
(
t
−
1
)
(
t
−
2
)
(
t
7
−
12
t
6
+
67
t
5
−
230
t
4
+
529
t
3
−
814
t
2
+
775
t
−
352
)
{\displaystyle t(t-1)(t-2)(t^{7}-12t^{6}+67t^{5}-230t^{4}+529t^{3}-814t^{2}+775t-352)}
彩色 さいしき 多項式 たこうしき には次 つぎ のような属性 ぞくせい がある。
P
(
G
,
0
)
=
0
{\displaystyle P(G,0)=0}
P
(
G
,
1
)
=
0
{\displaystyle P(G,1)=0}
(
G
{\displaystyle G}
に辺 あたり がある場合 ばあい )
P
(
G
,
t
)
=
0
{\displaystyle P(G,t)=0}
(
t
<
χ かい
(
G
)
{\displaystyle t<\chi (G)}
の場合 ばあい )
G
{\displaystyle G}
が
n
{\displaystyle n}
個 こ の頂点 ちょうてん 、
m
{\displaystyle m}
個 こ の辺 あたり 、
k
{\displaystyle k}
個 こ の連結 れんけつ 成分 せいぶん
G
1
,
G
2
,
{\displaystyle G_{1},G_{2},}
…,
G
k
{\displaystyle G_{k}}
から成 な るとき、
P
(
G
,
t
)
{\displaystyle P(G,t)}
の次数 じすう は
n
{\displaystyle n}
である。
P
(
G
,
t
)
{\displaystyle P(G,t)}
における
t
n
{\displaystyle t^{n}}
の係数 けいすう は 1 である。
P
(
G
,
t
)
{\displaystyle P(G,t)}
における
t
n
−
1
{\displaystyle t^{n-1}}
の係数 けいすう は
−
m
{\displaystyle -m}
である。
t
0
,
t
1
,
{\displaystyle t^{0},t^{1},}
…
t
k
−
1
{\displaystyle t^{k-1}}
の係数 けいすう は全 すべ てゼロである。
t
k
{\displaystyle t^{k}}
の係数 けいすう はゼロではない。
P
(
G
,
t
)
=
P
(
G
1
,
t
)
P
(
G
2
,
t
)
{\displaystyle P(G,t)=P(G_{1},t)P(G_{2},t)}
⋯
P
(
G
k
,
t
)
{\displaystyle P(G_{k},t)}
全 すべ ての彩色 さいしき 多項式 たこうしき の係数 けいすう は符号 ふごう が交互 こうご に変化 へんか する。
P
(
G
,
t
)
=
t
(
t
−
1
)
n
−
1
{\displaystyle P(G,t)=t(t-1)^{n-1}}
であるときのみ、
n
{\displaystyle n}
頂点 ちょうてん のグラフ G は木 き である。
単位 たんい 元 もと で評価 ひょうか された導 しるべ 関数 かんすう
P
′
(
G
,
1
)
{\displaystyle P'(G,1)}
は「彩色 さいしき 不変 ふへん 量 りょう (chromatic invariant)」
θ しーた
(
G
)
{\displaystyle \theta (G)}
である。
グラフの辺 あたり 彩色 さいしき とは、グラフの辺 あたり を彩色 さいしき するもので、1つの頂点 ちょうてん に接合 せつごう するそれぞれの辺 あたり が常 つね に別々 べつべつ の色 いろ になるように最適 さいてき 彩色 さいしき する。k 色 いろ を使 つか った辺 あたり 彩色 さいしき を「k -辺 あたり 彩色 さいしき 」と呼 よ び、辺 あたり 集合 しゅうごう をk 個 こ のマッチング に分割 ぶんかつ する問題 もんだい と等価 とうか である。グラフ G の辺 あたり 彩色 さいしき に必要 ひつよう な最小 さいしょう の色 いろ 数 すう を彩色 さいしき 指数 しすう (chromatic index) または辺 あたり 彩色 さいしき 数 すう (edge chromatic number) と呼 よ び、χ かい ′(G) で表 あらわ す。テイト彩色 さいしき (Tait coloring) とは、立方体 りっぽうたい グラフ (3-正則 せいそく グラフ )の3-辺 あたり 彩色 さいしき を意味 いみ する。四 よん 色 しょく 定理 ていり は、3-正則 せいそく で辺 あたり が交差 こうさ しない平面 へいめん グラフをテイト彩色 さいしき できることと等価 とうか である。
個々 ここ の頂点 ちょうてん にそれぞれ異 こと なる色 いろ を割 わ り当 あ てれば、その彩色 さいしき は正 ただ しい。従 したが って次 つぎ が成 な り立 た つ。
1
≤
χ かい
(
G
)
≤
n
{\displaystyle 1\leq \chi (G)\leq n\,}
1-彩色 さいしき 可能 かのう なのは辺 あたり のないグラフ に限 かぎ られる。n 個 こ の頂点 ちょうてん を持 も つ完全 かんぜん グラフ
K
n
{\displaystyle K_{n}}
を彩色 さいしき するには
χ かい
(
K
n
)
=
n
{\displaystyle \chi (K_{n})=n}
色 いろ が必要 ひつよう である。最適 さいてき な彩色 さいしき では、グラフ内 ない の m 個 こ 以上 いじょう の辺 あたり が色 いろ クラス間 あいだ を結 むす ぶ位置 いち にある。従 したが って、次 つぎ が成 な り立 た つ。
χ かい
(
G
)
(
χ かい
(
G
)
−
1
)
≤
2
m
{\displaystyle \chi (G)(\chi (G)-1)\leq 2m\,}
G に大 おお きさ k のクリーク が含 ふく まれている場合 ばあい 、そのクリークの彩色 さいしき に少 すく なくとも k 色 いろ を必要 ひつよう とする。い換 いか えれば、グラフ G の彩色 さいしき 数 すう について次 つぎ が成 な り立 た つ。
χ かい
(
G
)
≥
ω おめが
(
G
)
{\displaystyle \chi (G)\geq \omega (G)\,}
区間 くかん グラフ では、この境界 きょうかい がきつい。
2-彩色 さいしき 可能 かのう なグラフは常 つね に2部 ぶ グラフ であり、木 き や森 もり もそれに含 ふく まれる。四 よん 色 しょく 定理 ていり により、全 すべ ての平面 へいめん グラフは4-彩色 さいしき 可能 かのう である。
貪欲 どんよく 彩色 さいしき 法 ほう によれば、あらゆるグラフは頂点 ちょうてん の最大 さいだい 次数 じすう より1つ多 おお い色 いろ 数 すう で彩色 さいしき 可能 かのう である。
χ かい
(
G
)
≤
Δ でるた
(
G
)
+
1
{\displaystyle \chi (G)\leq \Delta (G)+1\,}
完全 かんぜん グラフは
χ かい
(
G
)
=
n
{\displaystyle \chi (G)=n}
かつ
Δ でるた
(
G
)
=
n
−
1
{\displaystyle \Delta (G)=n-1}
であり、奇 き 閉路 へいろ は
χ かい
(
G
)
=
3
{\displaystyle \chi (G)=3}
かつ
Δ でるた
(
G
)
=
2
{\displaystyle \Delta (G)=2}
である。したがってこの境界 きょうかい 条件 じょうけん はこれらのグラフでは彩色 さいしき 数 すう をよく限定 げんてい する。それら以外 いがい のグラフでは、境界 きょうかい 条件 じょうけん をさらに若干 じゃっかん 改良 かいりょう する余地 よち がある。ブルックスの定理 ていり [ 4] は次 つぎ の通 とお りである。
ブルックスの定理 ていり : 完全 かんぜん グラフでも奇 き 閉路 へいろ でもない単純 たんじゅん な連結 れんけつ グラフ G について
χ かい
(
G
)
≤
Δ でるた
(
G
)
{\displaystyle \chi (G)\leq \Delta (G)}
が成 な り立 た つ。
最大 さいだい クリークの大 おお きなグラフは彩色 さいしき 数 すう も大 おお きいが、逆 ぎゃく は必 かなら ずしも真 しん ではない。Grötzschグラフ(en )は4-彩色 さいしき 的 てき だが、三角形 さんかっけい を含 ふく まない(クリーク がない)。それを一般 いっぱん 化 か したグラフをMycielskian と呼 よ ぶ。
Mycielski の定理 ていり [ 5] : 三角形 さんかっけい を含 ふく まない、任意 にんい の彩色 さいしき 数 すう のグラフが存在 そんざい する。
ブルックスの定理 ていり から、彩色 さいしき 数 すう の大 おお きいグラフは次数 じすう が高 たか くなければならない。また、局所 きょくしょ 的 てき には大 おお きなクリークがあれば彩色 さいしき 数 すう は大 おお きくなる。しかし、彩色 さいしき 可能 かのう 性 せい はグラフの局所 きょくしょ 的 てき 現象 げんしょう ではない。内 うち 周 しゅう (最短 さいたん 閉路 へいろ の長 なが さ)が大 おお きいグラフは、局所 きょくしょ 的 てき に見 み れば木 き のようになっているが、その彩色 さいしき 数 すう は2になるとは限 かぎ らない。
定理 ていり (エルデシュ): 任意 にんい の内 うち 周 しゅう が大 おお きくかつ彩色 さいしき 数 すう の大 おお きいグラフが存在 そんざい する。
G の辺 あたり 彩色 さいしき は、そのライングラフ
L
(
G
)
{\displaystyle L(G)}
の頂点 ちょうてん 彩色 さいしき と等価 とうか であり、逆 ぎゃく も成 な り立 た つ。従 したが って、
χ かい
′
(
G
)
=
χ かい
(
L
(
G
)
)
{\displaystyle \chi '(G)=\chi (L(G))\,}
辺 あたり 彩色 さいしき 可能 かのう 性 せい とそのグラフの最大 さいだい 次数 じすう
Δ でるた
(
G
)
{\displaystyle \Delta (G)}
には強 つよ い関連 かんれん 性 せい がある。同 おな じ頂点 ちょうてん に接合 せつごう する全 すべ ての辺 あたり は異 こと なる色 いろ にしなければならないので、次 つぎ が成 な り立 た つ。
χ かい
′
(
G
)
≥
Δ でるた
(
G
)
{\displaystyle \chi '(G)\geq \Delta (G)\,}
さらに次 つぎ が成 な り立 た つ。
ケーニグの定理 ていり : G が2部 ぶ グラフ なら
χ かい
′
(
G
)
=
Δ でるた
(
G
)
{\displaystyle \chi '(G)=\Delta (G)}
一般 いっぱん に、この関係 かんけい はブルックスの定理 ていり が頂点 ちょうてん 彩色 さいしき に与 あた える関係 かんけい よりも強 つよ い。
Vizingの定理 ていり : 最大 さいだい 次数 じすう
Δ でるた
{\displaystyle \Delta }
のグラフの辺 あたり 彩色 さいしき 数 すう は
Δ でるた
{\displaystyle \Delta }
または
Δ でるた
+
1
{\displaystyle \Delta +1}
である。
平面 へいめん グラフでは、頂点 ちょうてん 彩色 さいしき は基本 きほん 的 てき に nowhere-zero flow と双対 そうつい 関係 かんけい にある。
無限 むげん グラフ については、まだよく判 わか っていない。無限 むげん グラフの彩色 さいしき について判明 はんめい している数少 かずすく ない事実 じじつ として次 つぎ の事柄 ことがら がある。
無限 むげん グラフ G の全 すべ ての有限 ゆうげん 部分 ぶぶん グラフが k -彩色 さいしき 可能 かのう であれば、選択 せんたく 公理 こうり を仮定 かてい した場合 ばあい にG 自体 じたい も同様 どうよう である(de Bruijn & Erdős 1951 )。
また、n ≥ n 0 の 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 の彩色 さいしき 多項式 たこうしき
P
(
G
,
t
)
{\displaystyle P(G,t)}
は
[
4
,
∞
)
{\displaystyle [4,\infty )}
の領域 りょういき でゼロにならないという予想 よそう を立 た てた。そのような彩色 さいしき 多項式 たこうしき が
[
5
,
∞
)
{\displaystyle [5,\infty )}
の領域 りょういき でゼロにならないことと、
P
(
G
,
4
)
≠
0
{\displaystyle P(G,4)\neq 0}
であることは判明 はんめい しているが、彼 かれ らの予想 よそう 自体 じたい は未解決 みかいけつ である。任意 にんい の2つのグラフの彩色 さいしき 多項式 たこうしき が同一 どういつ かどうかの判定 はんてい や、ある多項式 たこうしき が彩色 さいしき 多項式 たこうしき かどうかの判定 はんてい も未 み 解決 かいけつ の問題 もんだい である。
グラフ彩色 さいしき
決定 けってい 問題 もんだい
名称 めいしょう グラフ彩色 さいしき 、頂点 ちょうてん 彩色 さいしき 、k -彩色 さいしき
入力 にゅうりょく n 個 こ の頂点 ちょうてん を持 も つグラフ G 。整数 せいすう k
出力 しゅつりょく G は k 個 こ の色 いろ で最適 さいてき 彩色 さいしき 可能 かのう か?
時間 じかん 計算 けいさん 量 りょう O(2 n n )[ 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 n n )
複雑 ふくざつ 性 せい クラス#P完全 かんぜん
近似 きんじ 計算 けいさん 量 りょう 多項式 たこうしき 時間 じかん - 一部 いちぶ のケースのみ
非 ひ 近似 きんじ 計算 けいさん 量 りょう P=NPでない場合 ばあい 、多項式 たこうしき 時間 じかん アルゴリズムは存在 そんざい しない。
あるグラフが2色 しょく で彩色 さいしき 可能 かのう かどうかを決定 けってい する問題 もんだい は、そのグラフが2部 ぶ グラフ かどうかの決定 けってい 問題 もんだい と等価 とうか であり、幅優先 はばゆうせん 探索 たんさく を使 つか って多項式 たこうしき 時間 じかん で解 と ける。より一般 いっぱん 化 か すれば、パーフェクトグラフ の彩色 さいしき 数 すう と具体 ぐたい 的 てき な彩色 さいしき は半 はん 正 せい 定値 ていち 計画 けいかく 法 ほう を使 つか って多項式 たこうしき 時間 じかん で計算 けいさん できる。森 もり 、弦 つる グラフ 、閉路 へいろ グラフ 、車輪 しゃりん グラフ 、梯子 はしご グラフ といった種類 しゅるい のグラフは彩色 さいしき 多項式 たこうしき がわかっているので、多項式 たこうしき 時間 じかん での評価 ひょうか が可能 かのう である。
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})}
で行 おこな える[ 8] 。包 つつみ 除 じょ 原理 げんり と高速 こうそく ゼータ変換 へんかん のためのYates のアルゴリズムを使 つか えば、k -彩色 さいしき 可能 かのう 性 せい の判定 はんてい は任意 にんい のk について
O
(
2
n
n
)
{\displaystyle O(2^{n}n)}
の時間 じかん で行 おこな える[ 7] 。3-彩色 さいしき 可能 かのう 性 せい および4-彩色 さいしき 可能 かのう 性 せい の判定 はんてい についてはさらに高速 こうそく なアルゴリズムが知 し られており、それぞれ
O
(
1.3289
n
)
{\displaystyle O(1.3289^{n})}
[ 9] および
O
(
1.7504
n
)
{\displaystyle O(1.7504^{n})}
[ 10] の時間 じかん で判定 はんてい できる。
グラフ 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}
を除去 じょきょ したグラフを意味 いみ する。
P
(
G
−
u
v
,
k
)
{\displaystyle P(G-uv,k)}
はそのグラフの彩色 さいしき の組 く み合 あ わせ数 すう を表 あらわ し、u と v が同色 どうしょく の場合 ばあい もそうでない場合 ばあい も含 ふく まれる。上 うえ の式 しき から、彩色 さいしき の組 く み合 あ わせ数 すう は2つのグラフの彩色 さいしき 組 く み合 あ わせ数 すう の和 わ で表 あらわ される。頂点 ちょうてん u と v の色 いろ が異 こと なる場合 ばあい 、u と v が1つの辺 あたり で結 むす ばれたグラフでも同 おな じ彩色 さいしき が可能 かのう である。u と v が同色 どうしょく の場合 ばあい 、u と v を縮 ちぢみ 約 やく したグラフと同 おな じとみなすことができる。W・T・タット はこの漸 すすむ 化 か 式 しき を満 み たすグラフの属性 ぞくせい について興味 きょうみ を持 も ち、彩色 さいしき 多項式 たこうしき を一般 いっぱん 化 か したタット多項式 たこうしき を発見 はっけん した。
これらから、再帰 さいき 的 てき な手続 てつづ きが考 かんが えられ、それを削除 さくじょ ・縮 ちぢみ 約 やく アルゴリズム (deletion–contraction algorithm) と呼 よ び、多 おお くのグラフ彩色 さいしき アルゴリズムの基盤 きばん となっている。すなわち、与 あた えられたグラフを辺 あたり が1つ少 すく ない2つのグラフに変換 へんかん し、それを再帰 さいき 的 てき に繰 く り返 かえ すのである。これはフィボナッチ数 すう と同様 どうよう の再 さい 帰属 きぞく 性 せい を持 も ち、最悪 さいあく でも
(
(
1
+
5
)
/
2
)
n
+
m
=
O
(
1.6180
n
+
m
)
{\displaystyle ((1+{\sqrt {5}})/2)^{n+m}=O(1.6180^{n+m})}
の処理 しょり 時間 じかん となる[ 11] 。さらに入力 にゅうりょく されたグラフのスパニング木 き の数 かず
t
(
G
)
{\displaystyle t(G)}
の多項式 たこうしき の係数 けいすう を応用 おうよう することで解析 かいせき を改善 かいぜん することができる[ 12] 。実際 じっさい には、分 ぶん 枝 えだ 限定 げんてい 法 ほう を使 つか い、同型 どうけい のグラフを排除 はいじょ することで再帰 さいき 回数 かいすう を減 へ らすことができ、処理 しょり 時間 じかん は2つの頂点 ちょうてん を選 えら ぶ際 さい のヒューリスティックに依存 いぞん する。
同 おな じグラフにおいて2種類 しゅるい の頂点 ちょうてん の順序 じゅんじょ 付 づ けをしたときの貪欲 どんよく 彩色 さいしき 。うまく順序付 じゅんじょづ けすれば2-彩色 さいしき 可能 かのう だが、貪欲 どんよく 彩色 さいしき では
n
/
2
{\displaystyle n/2}
色 いろ まで費 つい やすことがある。
貪欲 どんよく 法 ほう では、頂点 ちょうてん に所定 しょてい の順序 じゅんじょ
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}
色 いろ を必要 ひつよう とすることがある。
頂点 ちょうてん を次数 じすう が小 ちい さくなる順序 じゅんじょ でソート すれば、貪欲 どんよく 彩色 さいしき で使 つか う最大 さいだい 色 しょく 数 すう は
max
i
min
{
d
(
x
i
)
+
1
,
i
}
{\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 について
χ かい
(
G
,
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-彩色 さいしき 問題 もんだい とみなすことができる。
^ M. Kubale, History of graph coloring , in Kubale (2004)
^ van Lint & Wilson (2001 , Chap. 33)
^ Jensen & Toft (1995 , p. 2)
^ Brooks (1941)
^ Mycielski (1955)
^ Heule, Marijn J.H. (2018), Computing Small Unit-Distance Graphs with Chromatic Number 5 , arXiv :1805.12181 , Bibcode : 2018arXiv180512181H
^ a b Björklund, Husfeldt & Koivisto (2006)
^ Lawler (1976)
^ Beigel & Eppstein (2005)
^ Byskov (2004)
^ Wilf (1986)
^ Sekine, Imai & Tani (1995)
^ Welsh & Powell (1967)
^ Brèlaz (1979)
^ Cole & Vishkin (1986) , see also Cormen, Leiserson & Rivest (1990 , Section 30.5)
^ Goldberg, Plotkin & Shannon (1988)
^ Barenboim & Elkin (2009) ; see also Kuhn (2009)
^ Leith (2006) and Duffy (2008)
^ Dailey (1980)
^ Halldórsson (1993)
^ Zuckerman (2007)
^ Guruswami & Khanna (2000)
^ Khot (2001)
^ Jaeger, Vertigan & Welsh (1990)
^ Goldberg & Jerrum (2008)
^ Holyer (1981)
^ Crescenzi & Kann (1998)
^ Marx (2004)
^ 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.3289n )”, 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
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