グラフ彩色

特に断りなく使用される場合、グラフの彩色とは、ほぼ常に適切な頂点彩色、すなわち、同じ辺を共有する2つの頂点が同じ色にならないようにグラフの頂点に色を割り当てることを指します。ループ（つまり、自身に直接つながる接続）を持つ頂点は決して適切に彩色できないため、この文脈におけるグラフはループを持たないものと理解されます。

頂点ラベルに色を使用する用語は、地図彩色に由来します。赤や青などのラベルは、色の数が少ない場合にのみ使用され、通常はラベルが整数{1, 2, 3, ...}から抽出されることが理解されています。

最大k色を使用する彩色を (適切な) k彩色と呼びます。グラフGを彩色するために必要な最小の色数を彩色数と呼び、しばしば χ( G ) と表記します。[ 5 ] χ ^{( G )}はグラフのオイラー標数を表すためにも使用されるため、γ ( G )が使用されることもあります。 ^{[ 6 ]} (適切な) 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 次グラフの 3 辺彩色です。4色定理は、すべての平面 3 次ブリッジレスグラフがテイト彩色を許容するという主張と同等です。

全彩色とは、グラフの頂点と辺に色を付ける方法の一種です。特に断りなく使用する場合、全彩色は常に、隣接する頂点、隣接する辺、および辺とその端点に同じ色が割り当てられないという意味で適切であるとみなされます。グラフGの全彩色数χ ″ ( G )は、 Gの任意の全彩色に必要な最小の色数です。

曲面上に強く埋め込まれたグラフの場合、面彩色問題は頂点彩色問題の双対問題となる。

向き付け可能な曲面上に強い埋め込みを持つグラフGについて、 William T. Tutte ^{[ 7 ] [ 8 ] [ 9 ]}は、グラフがk面彩色可能であれば、G はどこにもゼロがないkフローを持つことを発見した。曲面が球面の場合、同値性が成り立つ。

グラフの無色彩色とは、グラフの自己同型群の作用による彩色の軌道のことである。色はラベル付けされたままであり、無色となるのはグラフの方である。与えられた有限色集合からグラフの無色彩色の数を数える彩色多項式に相当するものがある。

d個の頂点を持つグラフの彩色を ⁠ のベクトルとして解釈すると${\displaystyle \mathbb {Z} ^{d}}$自己同型写像​​の作用は、彩色ベクトルの係数の置換である。

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

$1 ≤ χ(G) ≤ n。$

1色で着色できるグラフは、辺のないグラフのみです。完全グラフ${\displaystyle K_{n}}$n個の頂点には${\displaystyle \chi (K_{n})=n}$色。最適な彩色では、グラフのm個のエッジのうち少なくとも 1 つがすべての色のクラスのペア間に存在しなければならないので、

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

より一般的には家族$\displaystyle {\mathcal {F}}}$グラフのχ は、ある関数が存在する場合にχで制限されます。${\displaystyle c}$グラフが${\displaystyle G}$で$\displaystyle {\mathcal {F}}}$最大で着色可能${\displaystyle c(\omega (G))}$色、${\displaystyle \omega (G)}$は、​${\displaystyle G}$完全グラフの族の場合、この関数は次のようになります。${\displaystyle c(\omega (G))=\omega (G)}$。

2色で彩色可能なグラフは、木や森を含む二部グラフそのものです。4色定理により、すべての平面グラフは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}$したがって、これらのグラフではこの上限が最良です。その他のすべての場合、上限はわずかに改善できます。ブルックスの定理^{[ 10 ]}は、

ブルックスの定理：$\displaystyle \chi (G)\leq \Delta (G)$連結した単純グラフGの場合、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).$

ベクトル彩色数：${\displaystyle W}$正定値半行列で、${\displaystyle W_{i,j}\leq -{\tfrac {1}{k-1}}}$いつでも${\displaystyle (i,j)}$は、${\displaystyle G}$。 定義する$\displaystyle \chi _{V}(G)$このような行列の最小のkである${\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).}$

大きなクリークを持つグラフは彩色数が高いが、その逆は必ずしも真ではない。グロッツシュグラフは三角形を持たない4彩色グラフの一例であり、この例はミシエルスキアンに一般化できる。

定理（WT Tutte、1947年、^{[ 11 ]} Alexander Zykov、1949年、Jan Mycielski、1955年）：任意の高い彩色数を持つ三角形を含まないグラフが存在する。  

これを証明するために、MycielskiとZykovはそれぞれ、三角形を含まないグラフの帰納的に定義された族の構成を与えたが、彩色数は任意に大きかった。^{[ 12 ]} Burling（1965）は、軸に沿ったボックスを$\displaystyle \mathbb {R} ^{3}}$その交差グラフは三角形を含まず、適切に着色するには任意の数の色が必要となる。このグラフの族はバーリンググラフと呼ばれる。同じグラフのクラスは、Pawlik ら (2014) によって与えられた平面上の三角形を含まない線分の族の構築にも使用される。^{[ 13 ]}これは、その交差グラフの彩色数も任意に大きいことを示している。したがって、これは、軸に沿ったボックスが$\displaystyle \mathbb {R} ^{3}}$線分も同様に$\displaystyle \mathbb {R} ^{2}}$χで制限されていない。^{[ 13 ]}

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

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

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

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

エッジの着色可能性とグラフの最大次数には強い相関関係がある。${\displaystyle \Delta (G)}$同じ頂点に接続するすべての辺にはそれぞれ独自の色が必要なので、

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

さらに、

ケーニッヒの定理：${\displaystyle \chi '(G)=\デルタ(G)}$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 )。

上記のとおり、${\displaystyle \omega (G)\leq \chi (G)\leq \Delta (G)+1.}$1998年のリードの推測では、その値は本質的に下限に近い、$\displaystyle \chi (G)\leq \left\lceil {\frac {\omega (G)+\Delta (G)+1}{2}}\right\rceil .}$

2点が単位距離を持つ場合に隣接しているという平面の彩色数は、5、6、または7のいずれかであるが、未知である。グラフの彩色数に関するその他の未解決問題には、彩色数kを持つすべてのグラフは、k個の頂点を持つ完全グラフをマイナーとして持つというハドウィガー予想、各ペアに共通する頂点が最大で1つである完全グラフの和集合の彩色数を制限するエルデシュ・ファーバー・ロヴァース予想、 k彩色グラフの中で完全グラフは交差数が最小であるというアルバートソン予想などがある。

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

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

グラフが平面グラフで、かつ枝幅が小さい場合（または非平面グラフであっても枝分割が既知の場合）、動的計画法を用いて多項式時間で解くことができます。一般に、必要な時間はグラフのサイズに対して多項式時間ですが、枝幅に対しては指数関数的に増加します。

k彩色に対する総当たり探索では、${\displaystyle k^{n}}$n個の頂点にk色の割り当てを行い、それぞれが正当かどうかをチェックします。彩色数と彩色多項式を計算するために、この手順はすべての${\displaystyle k=1,\ldots ,n-1}$入力グラフが最小の場合を除いて、実用的ではない。

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

収縮​${\displaystyle G/uv}$グラフGの頂点uとvを識別し、それらの間の辺をすべて削除することによって得られるグラフは、uとvを識別して得られるグラフである。元々uまたはvに接続していた残りの辺は、識別された頂点（つまり、新しく統合されたノードuv）に接続される。この操作は、グラフ彩色解析において重要な役割を果たす。

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

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

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

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

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

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

これらの式は、グラフ彩色アルゴリズムの基礎となる削除・縮約アルゴリズムと呼ばれる再帰的手順を生み出します。実行時間はフィボナッチ数列と同じ漸化式を満たすため、最悪の場合でもアルゴリズムは多項式係数の範囲内で実行されます。${\displaystyle \left({\tfrac {1+{\sqrt {5}}}{2}}\right)^{n+m}=O(1.6180^{n+m})}$n個の頂点とm個の辺の場合。^{[ 23 ]}この解析は、数の多項式係数の範囲内で改善できる。${\displaystyle t(G)}$入力グラフの全域木。[ 24 ^]実際には、再帰呼び出しを回避するために、分岐限定法とグラフ同型性拒否法が採用されています。実行時間は、頂点ペアを選択するために使用されるヒューリスティックに依存します。

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

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

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

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

グラフ彩色におけるよく知られた多項式時間ヒューリスティックアルゴリズムとして、DSaturアルゴリズムと再帰的最大優先（RLF）アルゴリズムが挙げられる。

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

再帰的最大優先アルゴリズムは、各色クラスを一つずつ構築していくという異なる方法で動作します。このアルゴリズムは、特殊なヒューリスティックルールを用いてグラフ内の最大独立頂点集合を特定します。次に、これらの頂点を同じ色に割り当て、グラフから削除します。これらの操作は、頂点がなくなるまで残りの部分グラフに対して繰り返されます。

DSatur の最悪ケースの複雑さは${\displaystyle O(n^{2})}$、 どこ${\displaystyle n}$はグラフの頂点の数です。このアルゴリズムは、飽和度を格納するためにバイナリヒープを使用して実装することもできます。${\displaystyle O((n+m)\log n)}$どこ${\displaystyle m}$はグラフのエッジ数です。^{[ 27 ]}これにより、疎グラフでははるかに高速な実行が可能になります。RLF の全体的な複雑さは、 DSaturよりわずかに高く、${\displaystyle O(mn)}$[ ^{27 ]​}

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

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

分散アルゴリズムの分野では、グラフ彩色問題は対称性の破れ問題と密接に関連しています。現在の最先端のランダム化アルゴリズムは、最大次数Δが十分に大きい場合、決定論的アルゴリズムよりも高速です。最速のランダム化アルゴリズムは、SchneiderとWattenhoferによるマルチトライアル技術を採用しています。 ^{[ 28 ]}

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

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

最も単純で興味深いケースはnサイクルです。Richard Cole とUzi Vishkin ^{[ 29 ]}は、同期通信ステップ 1 回で色の数をnからO (log n )に削減する分散アルゴリズムが存在することを示しています。同じ手順を繰り返すことで、 O ( log * n ) 回の通信ステップでnサイクルの 3 色付けを得ることができます(一意のノード識別子があると仮定した場合)。  

関数log *（反復対数）は、非常にゆっくりと増加する関数であり、「ほぼ定数」です。そのため、Cole と Vishkin の結果は、nサイクルを 3 色で彩色するための定数時間分散アルゴリズムが存在するかどうかという疑問を提起しました。Linial (1992) は、これは不可能であることを示しました。決定論的な分散アルゴリズムでは、nサイクルのn色彩色を 3 色彩色に縮小するためにΩ( log * n ) 回の通信ステップが必要になります。 

コールとヴィシュキンによる手法は、任意の次数制限グラフにも適用可能であり、実行時間は poly(Δ) + O ( log * n ) である。^{[ 30 ]}この手法は、シュナイダーとワッテンホーファーによって単位円盤グラフに拡張された。 ^{[ 31 ]}小さな Δ に対する (Δ + 1) 彩色のための最速の決定論的アルゴリズムは、レオニード・バレンボイム、マイケル・エルキン、ファビアン・クーンによるものである。^{[ 32 ]}バレンボイムらのアルゴリズムは、O (Δ) + log * ( n )/2 の時間で実行され、定数係数 1/2 はリニアルの下限により改善できないため、nに関して最適である。パンコネシとスリニヴァサン (1996)は、ネットワーク分解を用いて Δ+1 彩色を時間で計算している。     ${\displaystyle 2^{O\left({\sqrt {\log n}}\right)}}$。

分散モデルでは、辺彩色問題も研究されている。Panconesi & Rizzi (2001) は、このモデルにおいてO (Δ + log * n ) 時間で(2Δ − 1) 彩色を実現している。Linial (1992)による分散頂点彩色の下限は、分散辺彩色問題にも適用できる。     

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

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

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

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

彩色多項式の係数を計算することは#P 困難です。実際、${\displaystyle \chi (G,k)}$は、 k = 1 およびk = 2を除く任意の有理点kで #P 困難です。^{[ 41 ]} NP = RPでない限り、 k = 2を除く任意の有理点k ≥ 1.5で彩色多項式を評価するFPRAS はありません。^{[ 42 ]}          

辺彩色に関しては、Vizingの結果の証明により、最大でΔ+1色を使用するアルゴリズムが得られます。ただし、辺彩色数の2つの候補値を決定することはNP完全です。^{[ 43 ]}近似アルゴリズムの観点から、Vizingのアルゴリズムは、辺彩色数が4/3以内で近似できることを示しており、困難性の結果は、P = NPでない限り、任意のε > 0に対して(4/3 − ε )アルゴリズムが存在しないことを示しています。これらは、近似アルゴリズムの文献の中で最も古い結果の1つですが、どちらの論文もその概念を明示的に使用していません。^{[ 44 ]}    

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

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

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

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

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

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

モジュラー彩色とは、各頂点の色が、その頂点に隣接する頂点の色の合計となるグラフ彩色の一種である。

させて${\displaystyle k\geq 2}$色は複数あり、${\displaystyle \mathbb {Z} _{k}}$は、整数のモジュロの集合です。${\displaystyle k}$要素（または色）から構成される${\displaystyle 0,1,2,...,k-2,k-1}$まず、各頂点を色付けします。${\displaystyle G}$要素を使用して${\displaystyle \mathbb {Z} _{k}}$隣接する2つの頂点に同じ色を割り当てることを可能にする。言い換えれば、${\displaystyle c}$着色料として${\displaystyle c:V(G)\rightarrow \mathbb {Z} _{k}}$隣接する頂点には同じ色を割り当てることができる。

各頂点について${\displaystyle v}$で${\displaystyle G}$色の合計${\displaystyle v}$、${\displaystyle \sigma (v)}$は、 に隣接するすべての頂点の合計です。${\displaystyle v}$モジュロ${\displaystyle k}$色の合計${\displaystyle v}$は、

${\displaystyle \sigma (v)=\sum _{u\in N(v)}c(u),}$

どこ${\displaystyle u}$は、の近傍にある任意の頂点である。${\displaystyle v}$、${\displaystyle N(v)}$次に、隣接する頂点の合計によって決定される新しい色で各頂点を着色します。グラフ${\displaystyle G}$モジュール式${\displaystyle k}$-隣接する頂点のペアごとに色付けする場合${\displaystyle a}$そして${\displaystyle b}$、${\displaystyle \sigma (a)\neq \sigma (b)}$. モジュラー彩色数${\displaystyle G}$、${\displaystyle mc(G)}$は、の最小値です。${\displaystyle k}$モジュラーが存在する${\displaystyle k}$-着色${\displaystyle G}$。

例えば、頂点があるとします${\displaystyle v}$割り当てられた色を持つ頂点に隣接${\displaystyle 0,1,1}$、 そして${\displaystyle 3{\bmod {4}}}$（つまり、${\displaystyle k=4}$) 色の合計は${\displaystyle \sigma (v)=(0+1+1+3){\bmod {4}}=5{\bmod {4}}=1{\bmod {4}}}$これは頂点の新しい色になります${\displaystyle v}$。このプロセスをすべての頂点に対して繰り返します。${\displaystyle G}$隣接する頂点のいずれも色の合計が等しくない場合、${\displaystyle G}$モジュロを持つ${\displaystyle 4}$着色。

符号付きグラフやゲイングラフについても、色付けを検討することができます。