Loading article…
グラフ理論において、ブルックスの定理はグラフの最大次数とその彩色数との関係を述べています。定理によれば、すべての頂点が最大 Δ 個の隣接頂点を持つ連結グラフでは、 Δ + 1 個の色を必要とする完全グラフと奇数長のサイクルグラフの 2 つのケースを除いて、頂点は Δ 個の色のみで彩色できます。
この定理は、1941年に証明を発表したR・レナード・ブルックスにちなんで名付けられました。 [1]ブルックスの定理で記述される色数による彩色は、ブルックス彩色[2]またはΔ彩色[3]と呼ばれることもあります。
正式な声明
最大次数Δを持つ任意の連結 無向グラフ Gについて、Gの彩色数は最大Δである。ただし、Gが完全グラフまたは奇数サイクルの場合は、彩色数はΔ + 1である。[1]
証拠
László Lovász は、ブルックスの定理の簡略化された証明を与えている。グラフが2 連結でない場合、その 2 連結成分を別々に彩色し、その後で彩色を組み合わせることができる。グラフにΔ 未満の次数を持つ頂点vがある場合、 vから遠い頂点を近い頂点よりも先に彩色する貪欲彩色アルゴリズムでは、最大で Δ 色しか使用しない。これは、v以外の各頂点が彩色される時点で、その近傍の少なくとも 1 つ ( vへの最短経路上にある頂点) が彩色されていないため、彩色された近傍の数が Δ 未満となり、自由な色を持つからである。アルゴリズムがv に到達すると、近傍の数が少ないため、それを彩色できる。したがって、証明の最も難しいケースは、 Δ ≥ 3 の 2 連結 Δ正則グラフに関するものである。この場合、Lovász は、ルートvの隣接しない 2 つの近傍uとwがツリーのリーフとなるスパニング ツリーを見つけることができることを示している。uとwから始めて、スパニングツリーの残りの頂点を下から上に処理し、vで終了する貪欲な彩色では、最大で Δ 色しか使用されません。なぜなら、 v以外のすべての頂点が彩色されている場合、その頂点には彩色されていない親があるため、すでに彩色されている隣接頂点はすべての空いている色を使い切ることができないのに対し、vでは2 つの隣接頂点uとw は同じ色であるため、 v自体にも空いている色が残るからです。[4]
拡張機能
この定理のより一般的なバージョンはリスト彩色にも適用されます。クリークでも奇数サイクルでもない最大次数 Δ の連結無向グラフと、各頂点の Δ 色のリストが与えられた場合、隣接する 2 つの頂点が同じ色にならないように、各頂点のリストから色を選択できます。言い換えると、連結無向グラフ G のリスト彩色数は、G がクリークまたは奇数サイクルでない限り、Δ を超えることはありません。[5]
グラフによっては、Δ色よりも少ない色数で済む場合もあります。Δが十分に大きい場合、グラフにΔクリークがない場合に限り、Δ − 1色で十分です。 [6]三角形のないグラフ、またはより一般的には各頂点の近傍が十分に疎なグラフの場合、O(Δ/log Δ)色数で十分です。[7]
グラフの次数は、他の種類の彩色の上限にも現れます。たとえば、辺彩色の場合、彩度指数は最大でも Δ + 1 であるという結果は、ビイジングの定理です。ブルックスの定理を全彩色に拡張して、全彩色数は最大でも Δ + 2 であると予想したことは、メディ・ベザドとビイジングによって提唱されています。公平な彩色に関するハジュナル・セメレディの定理は、任意のグラフには、任意の 2 つの色クラスのサイズが最大でも 1 だけ異なる (Δ + 1)-彩色が存在すると述べています。
アルゴリズム
次数ΔグラフのΔ色付け、さらにはΔリスト色付けは線形時間で見つけられる可能性がある。[8]並列および分散計算モデルでブルックス色付けを見つけるための効率的なアルゴリズムも知られている。[9]
注記
- ^ ab ブルックス（1941年）。
- ^ Hajnal & Szemerédi (1990).
- ^ パンコネージとスリニヴァサン (1995)。
- ^ ロヴァース（1975年）。
- ^ ヴィジング（1976年）。
- ^ リード（1999年）。
- ^ アロン、クリベレヴィッチ、スダコフ（1999年）。
- ^ スクルラッタナクルチャイ（2006年）。
- ^ カーロフ (1989);ハイナルとセメレディ (1990);パンコネージとスリニバサン (1995)。グラブルとパンコネージ (2000)。
参考文献
- アロン、ノガ、クリベレヴィッチ、マイケル、スダコフ、ベニー(1999)、「疎な近傍によるグラフの色付け」、Journal of Combinatorial Theory、シリーズ B、77 (1): 73–82、doi : 10.1006/jctb.1999.1910
- ブルックス、RL (1941)、「ネットワークのノードの色付けについて」、ケンブリッジ哲学協会数学紀要、37 (2): 194–197、Bibcode :1941PCPS...37..194B、doi :10.1017/S030500410002168X、S2CID 209835194。
- Grable, David A.; Panconesi, Alessandro (2000)、「Brooks–Vizing カラーリングの高速分散アルゴリズム」、Journal of Algorithms、37 : 85–120、doi :10.1006/jagm.2000.1097、S2CID 14211416。
- ピーター・ハイナル。Szemerédi、Endre (1990)、「Brooks Coloring inParallel」、SIAM Journal on Discrete Mathematics、3 (1): 74–80、doi :10.1137/0403008。
- Karloff, HJ (1989)、「ブルックスの定理のためのNCアルゴリズム」、理論計算機科学、68 (1): 89–103、doi :10.1016/0304-3975(89)90121-7。
- ロヴァース、L. (1975)、「グラフ理論における3つの短い証明」、組合せ理論ジャーナル、シリーズB、19 (3): 269–271、doi : 10.1016/0095-8956(75)90089-1。
- パンコネージ、アレッサンドロ; スリニヴァサン、アラヴィンド (1995)、「Δ-カラーリングの局所的性質とそのアルゴリズム的応用」、コンビナトリカ、15 (2): 255–280、doi :10.1007/BF01200759、S2CID 28307157。
- リード、ブルース(1999)、「ブルックスの定理の強化」、組合せ理論ジャーナル、シリーズ B、76 (2): 136–149、doi : 10.1006/jctb.1998.1891。
- Skulrattanakulchai, San (2006)、「線形時間でのΔ-リスト頂点カラーリング」、Information Processing Letters、98 (3): 101–106、doi :10.1016/j.ipl.2005.12.007。
- Vizing, VG (1976)、「与えられた色による頂点彩色」、Diskret. Analiz. (ロシア語)、29 : 3–10。
外部リンク
- ワイスシュタイン、エリック W.、「ブルックスの定理」、MathWorld