グラフ彩色
最大クリークの大きなグラフは彩色数も大きいが、逆は必ずしも真ではない。Grötzschグラフ(en)は4-彩色的だが、三角形を含まない(クリークがない)。それを一般化したグラフをMycielskianと呼ぶ。
Mycielskiの定理: 三角形を含まない、任意の彩色数のグラフが存在する。
ブルックスの定理から、彩色数の大きいグラフは次数が高くなければならない。また、局所的には大きなクリークがあれば彩色数は大きくなる。しかし、彩色可能性はグラフの局所的現象ではない。内周(最短閉路の長さ)が大きいグラフは、局所的に見れば木のようになっているが、その彩色数は2になるとは限らない。
定理(エルデシュ): 任意の内周が大きくかつ彩色数の大きいグラフが存在する。
グラフ彩色の分散アルゴリズムは、グラフの「対称性の破れ」の問題と密接に関連する。対称グラフでは、決定的分散アルゴリズムでは最適彩色を見つけることができない。対称性の破れを見つけるには何らかの予備的情報を必要とする。一般的な前提条件として、n 個の各頂点に {1, 2, ..., n} の一意の識別子を付与した状態、つまりそれぞれが別々の色に彩色された状態を初期状態とする。したがって、なすべきことは n 色を例えば Δ + 1 色にまで減らしていくことである。
貪欲法を単純に分散アルゴリズム化して(Δ + 1)-彩色を求めるアルゴリズムは、最悪の場合 Θ(n) 回の通信を必要とし、情報をネットワークの一端から全体に伝播させる必要があることもある。ただし、最大次数 Δ が小さければ、もっと高速なアルゴリズムも存在する。
単純で興味深い例として n-閉路グラフがある。Richard Cole と Uzi Vishkinによれば、1回の同期通信ステップで色数を n から O(log n) に減らす分散アルゴリズムが存在する。これを繰り返すとn-閉路グラフの3-彩色を O(log* n) の通信ステップで得ることができる(各頂点には一意の識別子が付与されていることが前提)。
グラフ彩色(グラフさいしょく、英: Graph coloring)とは、グラフの何らかの要素に、ある制約条件を満たすように色を割り当てることである。最も単純なものは、隣接する頂点同士が同じ色にならないように全頂点に彩色する問題である。これを頂点彩色(ちょうてんさいしょく)という。同様に辺彩色(へんさいしょく)は、隣接する辺同士が同じ色にならないように全辺を彩色する問題、面彩色(めんさいしょく)は、平面グラフの辺で囲まれた各領域(面)を隣接する面同士が同じ色にならないように彩色する問題である。