グラフの色付け

グラフ理論において、グラフの色付けはグラフのラベル付けの特殊なケースです。これは、特定の制約を受けるグラフの要素に、伝統的に「色」と呼ばれるラベルを割り当てることです。最も単純な形式では、グラフの頂点を、隣接する 2 つの頂点が同じ色にならないように色付けする方法です。これは、頂点の色付けと呼ばれます。同様に、辺の色付けでは、隣接する 2 つの辺が同じ色にならないように各辺に色を割り当てます。平面グラフの面の色付けでは、境界を共有する 2 つの面が同じ色にならないように各面または領域に色を割り当てます。

頂点彩色は、他の彩色問題を頂点彩色のインスタンスに変換できるため、グラフ彩色問題を導入するためによく使用されます。たとえば、グラフの辺彩色は、その線グラフの頂点彩色にすぎず、平面グラフの面彩色はその双対の頂点彩色にすぎません。ただし、非頂点彩色問題は、そのまま述べられ、研究されることがよくあります。これは、部分的には教育的なものであり、部分的には、辺彩色の場合のように、一部の問題は非頂点形式で研究するのが最適であるためです。

色を使用する慣習は、地図上の国を色付けすることから始まり、それぞれの面が文字通り色付けされます。これは、平面に埋め込まれたグラフの面を色付けすることに一般化されました。平面双対性により、頂点を色付けすることになり、この形式ですべてのグラフに一般化されます。数学的およびコンピュータ表現では、最初のいくつかの正または非負の整数を「色」として使用するのが一般的です。一般に、任意の有限集合を「色集合」として使用できます。色付けの問題の性質は、色の数によって決まりますが、色の数によって決まるわけではありません。

グラフの色付けには、理論的な課題だけでなく、多くの実用的な応用があります。古典的なタイプの問題に加えて、グラフ、色の割り当て方法、さらには色自体にさまざまな制限を設定することもできます。人気の数字パズルである数独の形で、一般の人々にも人気を博しています。グラフの色付けは、現在でも非常に活発な研究分野です。

注: この記事で使用されている多くの用語は、グラフ理論の用語集で定義されています。

グラフ彩色に関する最初の結果は、地図彩色の形でほぼ専ら平面グラフを扱っている。イングランドの州の地図を彩色しようとしていたとき、フランシス・ガスリーは四色予想を提唱し、共通の境界を共有する地域が同じ色にならないように地図を彩色するには4色で十分であると指摘した。ガスリーの兄弟はこの問題をユニバーシティ・カレッジの数学教師オーガスタス・ド・モーガンに伝え、ド・モーガンは1852年にウィリアム・ハミルトンに宛てた手紙の中でこの問題に言及した。アーサー・ケイリーは1879年のロンドン数学会でこの問題を提起した。同年、アルフレッド・ケンプは結果を確立したと主張する論文を発表し、10年間四色問題は解決済みとみなされた。ケンプは業績により王立協会の会員に選出され、後にロンドン数学会の会長となった。^[1]

1890年、パーシー・ジョン・ヒーウッドはケンプの議論が間違っていると指摘した。しかし、その論文でヒーウッドは五色定理を証明し、ケンプのアイデアを用いて、あらゆる平面地図は5色以上で着色できないと述べた。次の世紀には、膨大な研究が行われ、色の数を4色に減らす理論が開発され、最終的に1976年にケネス・アペルとヴォルフガング・ハーケンによって四色定理が証明された。証明はヒーウッドとケンプのアイデアまで遡り、その間の発展はほとんど無視された。^[2] 四色定理の証明は、1世紀も前の問題を解決したこととは別に、コンピュータを利用した最初の主要な証明であるという点でも注目に値する。

1912年、ジョージ・デイヴィッド・バーコフは彩色問題を研究するために彩色多項式を導入し、これはWTタットによってタット多項式に一般化されました。これらは両方とも代数グラフ理論における重要な不変量です。ケンペは1879年にすでに一般的な非平面の場合に注目しており、^[3] 20世紀初頭には平面グラフ彩色の高次曲面への一般化に関する多くの結果が続きました。

1960年、クロード・ベルジュはグラフ彩色に関する別の予想、強パーフェクトグラフ予想を定式化した。これはもともと、シャノンが導入したグラフのゼロエラー容量と呼ばれる情報理論的概念に触発されたものである。この予想は40年間未解決のままであったが、2002年にチュドノフスキー、ロバートソン、シーモア、トーマスによって有名な強パーフェクトグラフ定理として確立された。

グラフの色付けは、1970 年代初頭からアルゴリズムの問​​題として研究されてきました。彩色数問題 (以下のセクション§ 頂点の色付けを参照) は、1972 年のKarp の 21 個の NP 完全問題の 1 つであり、ほぼ同時期に、バックトラッキングと Zykov (1949) の削除-縮小再帰に基づくさまざまな指数時間アルゴリズムが開発されました。グラフの色付けの主要なアプリケーションの 1 つである コンパイラのレジスタ割り当ては、1981 年に導入されました。

グラフの色付けは、何の修飾もなしに使われる場合、ほとんどの場合、適切な頂点の色付け、つまり、同じ辺を共有する 2 つの頂点が同じ色にならないようにグラフの頂点に色を付けることを意味します。ループ(つまり、頂点自体に直接接続している)を持つ頂点は適切に色付けできないため、このコンテキストのグラフはループがないと理解されます。

頂点ラベルに色を使用するという用語の起源は、マップの色分けに遡ります。赤や青などのラベルは色の数が少ない場合にのみ使用され、通常はラベルは整数{ 1、2、3、...}から描画されると理解されています。

最大k色を使用する彩色は、（適切な） k彩色と呼ばれます。グラフG を彩色するために必要な最小の色の数は、その彩色数と呼ばれ、χ( G )と表記されることがよくあります。χ( G )はグラフのオイラー特性を表すためにも使用されるため、γ( G )が使用されることもあります。（適切な） k彩色を割り当てることができるグラフはk彩色可能であり、その彩色数がちょうどk である場合にk彩色です。同じ色が割り当てられた頂点のサブセットは色クラスと呼ばれ、そのようなクラスはすべて独立したセットを形成します。したがって、k彩色は頂点セットをk 個の独立したセットに分割することと同じであり、k部とk彩色可能という用語は同じ意味を持ちます。

彩色多項式は、与えられた数の色のうちいくつかを使ってグラフを色付けできる方法の数を数えます。たとえば、3 色を使うと、隣の画像のグラフは 12 通りの色付けができます。2 色だけだと、まったく色付けできません。4 色を使うと、24 + 4 × 12 = 72 通りの色付けができます。つまり、4 色すべてを使うと、4! = 24 通りの有効な色付けがあります ( 4 頂点のグラフに 4 色を割り当てると、すべて適切な色付けになります)。また、4 色のうち 3 色を選ぶと、12 通りの有効な 3 色付けがあります。したがって、例のグラフの場合、有効な色付けの数の表は次のようになります。

彩色多項式は、 Gのt色の数を数える関数P ( G , t )です。名前が示すように、与えられたGに対して、関数は確かにtの多項式です。例のグラフでは、P ( G , t ) = t ( t − 1) ² ( t − 2)であり、実際P ( G , 4) = 72 です。

彩色多項式には、彩色数よりもGの彩色可能性に関する多くの情報が含まれています。実際、 χは、彩色多項式χ( G ) = min{ k  : P ( G , k ) > 0}のゼロではない最小の正の整数です。

グラフの辺彩色は辺の適切な彩色であり、同じ色の2つの辺に頂点が接続されないように辺に色を割り当てることを意味します。k色による辺彩色はk辺彩色と呼ばれ、辺の集合をk 個の マッチングに分割する問題と同等です。グラフGの辺彩色に必要な最小の色の数は彩色指数、または辺彩色数χ ′( G )です。テイト彩色は、立方体グラフの3辺彩色です。4色定理は、すべての平面立方体の橋なしグラフがテイト彩色を許容する という主張と同等です。

全彩色は、グラフの頂点と辺の彩色の一種です。何の条件も付けずに使用する場合、全彩色は常に、隣接する頂点、隣接する辺、辺とその端の頂点に同じ色が割り当てられないという意味で適切であるとみなされます。グラフGの全彩色数χ ″( G )は、 Gの全彩色に必要な色数の最小値です。

表面上に強く埋め込まれたグラフの場合、面の色付けは 頂点の色付け問題の双対になります。

ウィリアム・T・タット^{[4] [5] [6]}は、有向面上に強い埋め込みを持つグラフGについて、グラフがk面彩色可能である場合、Gはどこでもゼロではないkフローを許容することを発見した。この同値性は、面が球面の場合にも成り立つ。

グラフのラベルなし彩色は、グラフの自己同型群の作用による彩色の軌道です。色はラベル付きのままで、ラベルが付いていないのはグラフです。与えられた有限の色集合からグラフのラベルなし彩色の数を数える 彩色多項式に類似したものが存在します。

d頂点のグラフの色付けを⁠ ⁠${\displaystyle \mathbb {Z} ^{d}}$内のベクトルとして解釈すると、自己同型の作用は色付けベクトル内の係数の 順列になります。

異なる頂点に異なる色を割り当てると、常に適切な色付けが得られるので、

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

1色にできるグラフは辺のないグラフだけです。n頂点の完全グラフ には色が必要です。最適な色付けでは、グラフのm辺のうち少なくとも1つは色クラスのペアの間に なければなりません。${\displaystyle K_{n}}$${\displaystyle \chi (K_{n})=n}$

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

より一般的には、グラフの族がχ有界であるとは、のグラフを最大で 色で着色できるような関数が存在する場合であり、完全グラフの族の場合、この関数は です。 ${\displaystyle {\mathcal {F}}}$${\displaystyle c}$${\displaystyle G}$${\displaystyle {\mathcal {F}}}$${\displaystyle c(\omega (G))}$${\displaystyle c(\omega (G))=\omega (G)}$

2 色に色付け可能なグラフは、木や森を含む2 部グラフそのものです。4 色定理により、すべての平面グラフは 4 色に色付けできます。

貪欲彩色は、すべてのグラフが最大頂点次数より1色多く彩色できることを示している。

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

完全グラフはと を持ち、奇数サイクルはと を持つので、これらのグラフではこの境界が最良である。他のすべてのケースでは、この境界はわずかに改善される。ブルックスの定理^[7]は次のように述べている。 ${\displaystyle \chi (G)=n}$${\displaystyle \Delta (G)=n-1}$${\displaystyle \chi (G)=3}$${\displaystyle \Delta (G)=2}$

ブルックスの定理: 連結された単純グラフGの場合、ただしGが完全グラフまたは奇数サイクルでない場合。${\displaystyle \chi (G)\leq \Delta (G)}$

色彩境界の下限値は長年にわたっていくつか発見されてきました。

Gにサイズkのクリークが含まれる場合、そのクリークを色付けするには少なくともk色が必要です。言い換えると、彩色数は少なくともクリーク数になります。

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

完全なグラフの場合、この境界は厳密です。クリークを見つけることはクリーク問題として知られています。

ホフマンの境界:が の辺でない場合は常にとなる実対称行列を とします。 を定義します。ここで はの最大固有値と最小固有値です。を定義します。ここで は上記と同じです。すると、次のようになります。 ${\displaystyle W}$${\displaystyle W_{i,j}=0}$${\displaystyle (i,j)}$${\displaystyle G}$${\displaystyle \chi _{W}(G)=1-{\tfrac {\lambda _{\max }(W)}{\lambda _{\min }(W)}}}$${\displaystyle \lambda _{\max }(W),\lambda _{\min }(W)}$${\displaystyle W}$${\textstyle \chi _{H}(G)=\max _{W}\chi _{W}(G)}$${\displaystyle W}$

${\displaystyle \chi _{H}(G)\leq \chi (G).}$

ベクトル彩色数:が の辺であるときは常にとなるような正の半定値行列を とします。をそのような行列が存在する最小の k と。すると ${\displaystyle W}$${\displaystyle W_{i,j}\leq -{\tfrac {1}{k-1}}}$${\displaystyle (i,j)}$${\displaystyle G}$${\displaystyle \chi _{V}(G)}$${\displaystyle W}$

${\displaystyle \chi _{V}(G)\leq \chi (G).}$

ロヴァース数:補グラフのロヴァース数は彩色数の下限でもある:

${\displaystyle \vartheta ({\bar {G}})\leq \chi (G).}$

分数彩色数:グラフの分数彩色数は彩色数の下限でもあります。

${\displaystyle \chi _{f}(G)\leq \chi (G).}$

これらの境界は次のように順序付けられます。

${\displaystyle \chi _{H}(G)\leq \chi _{V}(G)\leq \vartheta ({\bar {G}})\leq \chi _{f}(G)\leq \chi (G).}$

大きなクリークを持つグラフは彩色数が高くなりますが、その逆は当てはまりません。Grötzschグラフは三角形のない 4 彩色グラフの例であり、この例はMycielskiansに一般化できます。

定理（ウィリアム・T・タット 1947、^[8]アレクサンダー・ジコフ1949、ヤン・ミシェルスキ 1955）：任意の高い彩色数を持つ三角形のないグラフが存在する。

これを証明するため、Mycielski と Zykov の両者は、それぞれ、三角形のないグラフだが彩色が任意に大きい、帰納的に定義されたグラフ族の構成を示した。^[9] Burling (1965) は、交差グラフが三角形を持たず、適切に色付けするには任意の数の色を必要とする軸に沿ったボックスを構築した。このグラフ族は Burling グラフと呼ばれる。同じグラフのクラスは、Pawlik ら (2014) によって与えられた平面上の三角形のない線分の族の構築にも使用されている。^[10]これは、交差グラフの彩色が任意に大きいことを示している。したがって、これは の軸に沿ったボックスと の線分がχ有界ではないことを意味する。^[10]${\displaystyle \mathbb {R} ^{3}}$${\displaystyle \mathbb {R} ^{3}}$${\displaystyle \mathbb {R} ^{2}}$

ブルックスの定理によれば、彩色数の高いグラフは最大次数も高いはずです。しかし、彩色可能性は完全に局所的な現象ではありません。内周の大きいグラフは、すべての閉路が長いため局所的には木のように見えますが、彩色数は 2 である必要はありません。

定理（エルデシュ）：任意の大きさの内周と彩色数を持つグラフが存在する。^[11]

Gの辺彩色はその線グラフ の頂点彩色であり、その逆も同様である。したがって、 ${\displaystyle L(G)}$

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

辺の彩色可能性とグラフの最大次数の間には強い関係がある。同じ頂点に接する辺はすべて独自の色を必要とするため、 ${\displaystyle \Delta (G)}$

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

さらに、

ケーニッヒの定理: Gが二部構成の場合。${\displaystyle \chi '(G)=\Delta (G)}$

一般に、この関係はブルックスの定理が頂点彩色に対して示す関係よりもさらに強いです。

ヴィジングの定理:最大次数のグラフには辺彩色数または が。${\displaystyle \Delta }$${\displaystyle \Delta }$${\displaystyle \Delta +1}$

グラフがk色を持つのは、最長パスの長さが最大でkである非巡回方向を持つ場合のみです。これはGallai–Hasse–Roy–Vitaver 定理です(Nešetřil & Ossona de Mendez 2012)。

平面グラフの場合、頂点の色付けは本質的に、どこにもゼロがないフローと双対になります。

無限グラフについては、ほとんど知られていません。以下は、無限グラフの色付けに関する数少ない結果のうちの 2 つです。

• 無限グラフ Gのすべての有限サブグラフがk色可能である場合、選択公理の仮定の下で、Gも k色可能です。これは、de Bruijn & Erdős (1951) のde Bruijn–Erdős 定理です。
• グラフが任意のn ≥ n ₀に対して完全なn色付けを許容する場合、それは無限の完全な色付けを許容します (Fawcett 1978)。

上で述べたように、1998年のリードの推測では、その値は基本的に下限に近いとされている。 ${\displaystyle \omega (G)\leq \chi (G)\leq \Delta (G)+1.}$${\displaystyle \chi (G)\leq \left\lceil {\frac {\omega (G)+\Delta (G)+1}{2}}\right\rceil .}$

2 点が単位距離であれば隣接する平面の彩色数は未知ですが、5、6、または 7 のいずれかです。グラフの彩色数に関するその他の未解決問題には、彩色数kを持つすべてのグラフには、マイナーとしてk頂点上の完全グラフが存在するというHadwiger 予想、各ペアに共通する頂点が最大で 1 つである完全グラフの和の彩色数を上限とするErdős–Faber–Lovász 予想、 k彩色グラフの中で交差数 が最小のグラフが完全グラフであるというAlbertson 予想などがあります。

バーコフとルイスが 4 色定理への攻撃で彩色多項式を導入したとき、彼らは平面グラフGに対して、多項式は領域 に零点を持たないと予想しました。そのような彩色多項式は領域 に零点を持たないこと、および であることがわかっていますが、彼らの予想はまだ解決されていません。同じ彩色多項式を持つグラフを特徴付け、どの多項式が彩色であるかを決定することも未解決の問題です。 ${\displaystyle P(G,t)}$${\displaystyle [4,\infty )}$${\displaystyle [5,\infty )}$${\displaystyle P(G,4)\neq 0}$

グラフの色付け
決断
名前	グラフカラーリング、頂点カラーリング、kカラーリング
入力	n頂点を持つグラフG。整数k
出力	G はk色による適切な頂点彩色を許容しますか?
実行時間	O (2 n n ) [12]
複雑	NP完全
削減額	3-満足度
ゲイリー・ジョンソン	GT4
最適化
名前	彩度数
入力	n個の頂点を持つグラフG。
出力	χ (ジー)
複雑	NP困難
近似可能性	O ( n  (log  n ) −3  (log log  n ) 2 )
近似不可能性	P = NPでない限り、 O ( n 1− ε )
数える問題
名前	彩色多項式
入力	n頂点を持つグラフG。整数k
出力	Gの適切なk色付けの数P  ( G , k )
実行時間	（2nn）​​
複雑	♯P完了
近似可能性	制限されたケースに対するFPRAS
近似不可能性	P = NPでない限りPTASは存在しない

グラフを 2 色で着色できるかどうかを判断することは、グラフが二部グラフであるかどうかを判断することと同等であり、したがって幅優先探索または深さ優先探索を使用して線形時間で計算できます。より一般的には、完全グラフの彩色数とそれに対応する着色は、 半正定値計画法を使用して多項式時間で計算できます。彩色多項式の閉じた式は、フォレスト、弦グラフ、サイクル、ホイール、ラダーなど、多くのグラフのクラスで知られているため、これらは多項式時間で評価できます。

グラフが平面で、枝幅が狭い場合 (または非平面だが枝分解が既知である場合)、動的計画法を使用して多項式時間で解決できます。一般に、必要な時間はグラフのサイズに対して多項式ですが、枝幅に対しては指数関数的です。

k色付けのブルートフォース検索では、 n頂点へのk色の割り当てをそれぞれ検討し、それぞれが正当であるかどうかを確認します。彩色数と彩色多項式を計算するために、この手順はすべての に対して使用されますが、最小の入力グラフを除いて実用的ではありません。 ${\displaystyle k^{n}}$${\displaystyle k=1,\ldots ,n-1}$

動的計画法と最大独立集合の数の上限を用いると、k色可能性は時間と空間で決定できる。^[13]包含排他原理と高速ゼータ変換のためのYatesのアルゴリズムを用いると、任意のkに対してk色可能性を時間で決定できる^{[12] [14] [15] [16]}。より高速なアルゴリズムは 3 色可能性と 4 色可能性で知られており、それぞれ時間で決定できる^[17]と[ ^18]。また、5 色可能性と 6 色可能性、およびスパースグラフを含む制限されたグラフ族に対しては、指数関数的に高速なアルゴリズムが知られている。^[19]${\displaystyle O(2.4423^{n})}$${\displaystyle O(2^{n}n)}$${\displaystyle O(1.3289^{n})}$${\displaystyle O(1.7272^{n})}$

グラフGの縮約 は、 頂点uとv を識別し、それらの間の辺を削除することによって得られるグラフです。元々uまたはvに接続していた残りの辺は、それらの識別に接続されます (つまり、新しい融合ノードuv )。この操作は、グラフの色付けの分析で重要な役割を果たします。 ${\displaystyle G/uv}$

彩色数は再帰関係を満たす:

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

Zykov (1949) によるもので、uとv は隣接しない頂点であり、 はエッジuvが追加されたグラフです。いくつかのアルゴリズムはこの再帰の評価に基づいており、結果として得られる計算ツリーは Zykov ツリーと呼ばれることもあります。実行時間は、頂点uとv を選択するためのヒューリスティックに基づいています。 ${\displaystyle G+uv}$

彩色多項式は次の再帰関係を満たす。

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

ここで、uとv は隣接する頂点であり、はエッジuvが削除されたグラフです。は、グラフの可能な適切な彩色の数を表します。頂点は同じ色または異なる色を持つことができます。この場合、適切な彩色は 2 つの異なるグラフから生じます。説明するために、頂点uとv が異なる色を持つ場合、 uとvが隣接するグラフを検討してもよいでしょう。uとv が同じ色を持つ場合、 uとvが縮約されたグラフを検討してもよいでしょう。他のどのグラフ特性がこの再発を満たすかに関する Tutte の好奇心から、彼は彩色多項式の 2 変量一般化であるTutte 多項式を発見しました。 ${\displaystyle G-uv}$${\displaystyle P(G-uv,k)}$

これらの式から、削除–縮小アルゴリズムと呼ばれる再帰的手順が生成され、これはグラフの色付けのための多くのアルゴリズムの基礎を形成します。実行時間はフィボナッチ数列と同じ再帰関係を満たすため、最悪の場合でも、アルゴリズムはn頂点とm辺に対しての多項式係数以内の時間で実行されます。 ^[20]解析は、入力グラフの全域木の数の多項式係数以内に改善できます。 ^[21]実際には、分岐限定戦略とグラフ同型性拒否を使用して、再帰呼び出しの一部が回避されます。実行時間は、頂点ペアの選択に使用されるヒューリスティックによって異なります。 ${\displaystyle \left({\tfrac {1+{\sqrt {5}}}{2}}\right)^{n+m}=O(1.6180^{n+m})}$${\displaystyle t(G)}$

貪欲アルゴリズムは、頂点 を特定の順序、...、で検討し、 、...、の中で の隣接頂点で使用されていない最小の利用可能な色を に割り当て 、必要に応じて新しい色を追加します。結果の色付けの品質は、選択した順序によって異なります。最適な色数で貪欲な色付けにつながる順序付けが存在します。一方、貪欲な色付けは任意に悪い場合があります。たとえば、n頂点のクラウン グラフは2 色にできますが、色で貪欲な色付けにつながる順序付けがあります。 ${\displaystyle v_{1}}$${\displaystyle v_{n}}$${\displaystyle v_{i}}$${\displaystyle v_{i}}$${\displaystyle v_{1}}$${\displaystyle v_{i-1}}$${\displaystyle \chi (G)}$${\displaystyle n/2}$

弦グラフ、および区間グラフや無差別グラフなどの弦グラフの特殊なケースでは、グラフの完全消去順序の逆になるように頂点順序を選択することで、貪欲彩色アルゴリズムを使用して多項式時間で最適な彩色を見つけることができます。完全に順序付け可能なグラフはこの特性を一般化しますが、これらのグラフの完全な順序付けを見つけることは NP 困難です。

頂点が次数に従って順序付けられている場合、結果として得られる貪欲彩色では最大で色、つまりグラフの最大次数より最大で 色多く使用されます。このヒューリスティックは、ウェルシュ・パウエルアルゴリズムと呼ばれることもあります。^[22]ブレラズによる別のヒューリスティックは、アルゴリズムが進行中に順序を動的に確立し、次に最も多くの異なる色に隣接する頂点を選択します。^[23]他の多くのグラフ彩色ヒューリスティックも同様に貪欲彩色に基づいており、頂点を順序付ける特定の静的または動的戦略に基づいており、これらのアルゴリズムは順次彩色アルゴリズムと呼ばれることもあります。 ${\displaystyle {\text{max}}_{i}{\text{ min}}\{d(x_{i})+1,i\}}$

この数を最大化するように選択された頂点順序を使用して貪欲アルゴリズムによって取得できる最大 (最悪) の色数は、グラフの グランディ数と呼ばれます。

グラフの色付けのためのよく知られた 2 つの多項式時間ヒューリスティックは、DSatur アルゴリズムと再帰最大優先(RLF) アルゴリズムです。

貪欲な色付けアルゴリズムと同様に、DSatur はグラフの頂点を1 つずつ色付けし、必要に応じて未使用の色を消費します。新しい頂点が色付けされると、アルゴリズムは残りの色付けされていない頂点のうち、近傍に最も多くの異なる色がある頂点を決定し、次にこの頂点を色付けします。これは、特定の頂点の 彩度として定義されます。

再帰最大優先アルゴリズムは、各カラー クラスを 1 つずつ構築するという異なる方法で動作します。これは、特殊なヒューリスティック ルールを使用してグラフ内の最大独立頂点セットを識別することによって行われます。次に、これらの頂点を同じ色に割り当て、グラフから削除します。これらのアクションは、頂点がなくなるまで残りのサブグラフで繰り返されます。

DSatur の最悪の場合の複雑度はで、 はグラフの頂点の数です。このアルゴリズムは、 で動作する飽和度を格納するバイナリヒープを使用して実装することもできます。はグラフの辺の数です。^[24]これにより、スパースグラフでの実行が大幅に高速化されます。RLF の全体的な複雑度は でDSaturよりわずかに高くなります。^[24]${\displaystyle O(n^{2})}$${\displaystyle n}$${\displaystyle O((n+m)\log n)}$${\displaystyle m}$${\displaystyle O(mn)}$

DSaturとRLFは二部グラフ、サイクルグラフ、ホイールグラフに対して正確である。^[24]

χ彩色グラフは、決定論的 LOCAL モデルで、ラウンドでc色にできることが知られています。 一致するラウンドの下限も知られています。 この下限は、おそらく事前に共有されたエンタングルメント状態を使用して量子情報を交換できる量子コンピューターが許可された場合でも保持されます。 ${\displaystyle O(n^{1/\alpha })}$${\displaystyle \alpha =\left\lfloor {\frac {c-1}{\chi -1}}\right\rfloor }$${\displaystyle \Omega (n^{1/\alpha })}$

分散アルゴリズムの分野では、グラフの色付けは対称性の破れの問題と密接に関係している。現在の最先端のランダム化アルゴリズムは、最大次数Δが十分に大きい場合、決定論的アルゴリズムよりも高速である。最も高速なランダム化アルゴリズムは、シュナイダーとワッテンホファーによるマルチトライアル手法を採用している。 ^[25]

対称グラフでは、決定論的分散アルゴリズムでは適切な頂点彩色を見つけることができません。対称性を破るためには、何らかの補助情報が必要です。標準的な仮定は、各ノードが最初に一意の識別子（たとえば、集合 {1, 2, ..., n } から）を持っていることです。言い換えると、n彩色が与えられていると仮定します。課題は、色の数をnから、たとえば Δ + 1 に減らすことです。使用する色が多いほど、たとえば Δ + 1 ではなくO (Δ) を使用すると、必要な通信ラウンドが少なくなります。^[25]

(Δ + 1)-カラーリングの貪欲アルゴリズムの単純な分散バージョンでは、最悪の場合、Θ( n )回の通信ラウンドが必要になります。つまり、ネットワークの一方側から他方側に情報を伝播させる必要がある場合があります。

最も単純で興味深いケースはnサイクルです。リチャード・コールとウジ・ヴィシュキン^{[26]は、1回の同期通信ステップで色の数を}nからO (log  n )に減らす分散アルゴリズムがあることを示しています。同じ手順を繰り返すことで、 O ( log * n )の通信ステップでnサイクルの3色化を実現できます（一意のノード識別子があると仮定）。  

関数log *、反復対数は、極めてゆっくりと増加する関数であり、「ほぼ一定」です。したがって、Cole と Vishkin の結果から、nサイクルの 3 色付けを行う定数時間の分散アルゴリズムが存在するかどうかという疑問が生じました。Linial (1992) は、これは不可能であることを示しました。つまり、決定論的な分散アルゴリズムでは、nサイクルでn色付けを 3 色付けに減らすために、 Ω( log * n ) の通信ステップが必要です。  

Cole と Vishkin による手法は、任意の制限次数グラフにも適用でき、実行時間は poly(Δ) + O ( log *  n ) です。^{[27]この手法は、Schneider と Wattenhofer によって}単位ディスクグラフに拡張されました。^[28]小さな Δ に対する (Δ + 1) 色付けの最速の決定論的アルゴリズムは、Leonid Barenboim、Michael Elkin、Fabian Kuhn によるものです。^[29] Barenboim らによるアルゴリズムは、O (Δ) +  log * ( n )/2 の時間で実行され、定数係数 1/2 は Linial の下限により改善できないため、 nに関して最適です。Panconesi と Srinivasan (1996) は、ネットワーク分解を使用して の時間で Δ+1 色付けを計算しました。 ${\displaystyle 2^{O\left({\sqrt {\log n}}\right)}}$

分散モデルでは、エッジカラーリングの問題も研究されています。Panconesi & Rizzi (2001) は、このモデルで (2Δ − 1) カラーリングをO (Δ +  log *  n ) 時間で実現しました。Linial (1992) による分散頂点カラーリングの下限は、分散エッジカラーリング問題にも適用されます。

分散型アルゴリズムは、メッセージの受け渡しが許可されないアルゴリズムです（ローカルなメッセージの受け渡しが行われる分散型アルゴリズムとは対照的です）。適切な色付けが存在する場合にグラフを色付けする効率的な分散型アルゴリズムが存在します。これらのアルゴリズムは、頂点が、その隣接する頂点のいずれかが頂点と同じ色を使用しているかどうか、つまりローカルな競合が存在するかどうかを感知できることを前提としています。これは多くのアプリケーションで控えめな仮定です。たとえば、無線チャネル割り当てでは、ステーションが他の干渉送信機が同じチャネルを使用しているかどうかを検出できると想定するのが通常合理的です（たとえば、SINRを測定することによって）。この感知情報は、学習オートマトンに基づくアルゴリズムが確率1で適切なグラフの色付けを見つけるのに十分です。^[30]

グラフの彩色は計算的に困難である。k ∈ {0,1,2}の場合を除いて、 与えられたグラフが与えられたkに対してk彩色を許容するかどうかを決定することはNP 完全である。特に、彩色数を計算することは NP 困難である。 ^[31] 3 彩色問題は、4 正則平面グラフでも NP 完全である。^[32]しかし、最大次数が 3 以下のグラフでは、ブルックスの定理により、3 彩色問題は線形時間で解くことができる。さらに、すべてのk > 3 に対して、4 色定理により平面グラフのk彩色が存在し、そのような彩色を多項式時間で見つけることができる。しかし、平面グラフの辞書式最小の 4 彩色を見つけることは NP 完全である。^[33]

最もよく知られている近似アルゴリズムは、彩色数の係数O ( n (log log  n ) ² (log n) ^{−3 ) 以内のサイズの彩色を計算する。 [34]すべての}ε > 0に対して 、彩色数をn ^{1 − ε}内で近似することはNP 困難である。^[35]

3色に色付け可能なグラフを5色で色付けすることもNP困難である^[36]。4色に色付け可能なグラフを7色で色付けすることもNP困難である[ ³⁶ ] 。k≥5の場合にk色付け可能なグラフを色付けすることもNP困難である^[37]。${\displaystyle \textstyle {\binom {k}{\lfloor k/2\rfloor }}-1}$

彩色多項式の係数を計算するのは♯P 困難です。実際、 の値を計算することさえ、k  = 1 とk  = 2を除く任意の有理点kでは ♯P 困難です。[ ^38] NP  =  RPでない限り、 k  = 2を除く任意の有理点k  ≥ 1.5で彩色多項式を評価するFPRAS は存在しません。^[39]${\displaystyle \chi (G,k)}$

エッジカラーリングについては、ヴィイジングの結果の証明は最大 Δ+1 色を使用するアルゴリズムを与える。しかし、エッジ彩色数の 2 つの候補値の間で決定することは NP 完全である。^[40]近似アルゴリズムに関しては、ヴィイジングのアルゴリズムはエッジ彩色数が 4/3 以内に近似できることを示し、困難性の結果は P = NPでない限り、任意のε > 0に対して (4/3 − ε ) アルゴリズムが存在しないことを示す。どちらの論文でもその概念を明示的に使用していないにもかかわらず、これらは近似アルゴリズムの文献の中で最も古い結果の 1 つである。^[41]

頂点彩色モデルは、多くのスケジューリング問題に適用できます。^[42]最も単純な形式では、与えられた一連のジョブをタイムスロットに割り当てる必要があり、各ジョブにはそのようなスロットが 1 つ必要です。ジョブは任意の順序でスケジュールできますが、ジョブのペアは、たとえば共有リソースに依存している場合など、同じタイムスロットに割り当てられない可能性があるという意味で競合する場合があります。対応するグラフには、すべてのジョブの頂点と、競合するジョブのペアごとに 1 つの辺が含まれます。グラフの彩色数は、すべてのジョブを競合なしで完了するのに最適な時間である 最小メイクスパンとまったく同じです。

スケジューリング問題の詳細によってグラフの構造が定義されます。たとえば、航空機をフライトに割り当てる場合、結果として得られる競合グラフは間隔グラフであるため、色付け問題を効率的に解決できます。無線局への帯域幅割り当てでは、結果として得られる競合グラフは単位ディスクグラフであるため、色付け問題は 3 近似可能です。

コンパイラは、あるコンピュータ言語を別の言語に変換するコンピュータ プログラムです。生成されたコードの実行時間を改善するために、コンパイラの最適化手法の 1 つにレジスタ割り当てがあります。レジスタ割り当てでは、コンパイルされたプログラムで最も頻繁に使用される値が高速プロセッサ レジスタに保持されます。理想的には、値は、使用時にすべてレジスタ内に存在するようにレジスタに割り当てられます。

この問題に対する教科書的なアプローチは、グラフ着色問題としてモデル化することです。^[43]コンパイラは 干渉グラフを構築します。ここで、頂点は変数であり、辺は2つの頂点が同時に必要な場合にそれらの頂点を接続します。グラフをk色で着色できる場合、同時に必要な変数のセットは最大k個のレジスタに格納できます。

グラフの色付けの問題は、スポーツのスケジュール作成、^[44]、座席​​表の作成、^[45]、試験の時間割作成、^[46]、タクシーのスケジュール作成、^[47]、数独パズルの解決など、多くの実用的な分野で発生します。^[48]

不適切な彩色問題の重要なクラスは、ラムゼー理論で研究されています。この理論では、グラフの辺に色が割り当てられ、接続する辺の色に制限はありません。簡単な例としては、友人と他人の定理があります。これは、6 つの頂点を持つ完全グラフの辺をどのような彩色にしても、単色の三角形が存在するというものです。これは、6 人のグループには、3 人が互いに他人であるか、3 人が互いに知り合いである、という形でよく説明されます。ラムゼー理論は、この考え方を一般化して無秩序の中に規則性を求めること、つまり、与えられた構造を持つ単色の部分グラフが存在するための一般的な条件を見つけることに関係しています。 ${\displaystyle K_{6}}$

符号付きグラフやゲイングラフでも色付けを考慮することができます。

• クリティカルグラフ
• グラフ塗り絵ゲーム
• グラフ準同型
• ハヨス建設
• 数独の数学
• 多部グラフ
• 独自に色付け可能なグラフ

• 高性能グラフ カラーリング アルゴリズム 書籍『A Guide to Graph Colouring: Algorithms and Applications』(Springer International Publishers、2015 年) で使用されている 8 つの異なるアルゴリズム (C++ で実装) のスイートです。
• Joseph Culberson によるグラフ カラーリング ページ (グラフ カラーリング プログラム)
• ジム・アンドリュースとマイク・フェローズによるCoLoRaTiOnはグラフカラーリングパズルです
• グラフカラーリングのソースコードへのリンク 2008-07-04 にWayback Machineでアーカイブされました
• Tutte、Chromatic、Flow 多項式を効率的に計算するコード。2008-04-16 にGary Haggard、David J. Pearce、Gordon Royle によってWayback Machineにアーカイブされました。
• Jose Antonio Martin H. によるグラフカラーリング Web アプリ。