ヴィジングの定理

グラフ理論において、ヴィジングの定理は、すべての単純な無向グラフは、最大次数Δより最大で 1 大きい色数を使用して辺を彩色できると述べている。少なくともΔ色は常に必要なので、無向グラフはΔ色で十分な「クラス 1」グラフとΔ + 1色が必要な「クラス 2」グラフの 2つのクラスに分けられる。ヴィジングの定理のより一般的なバージョンでは、ループのないすべての無向多重グラフは最大でΔ+µ色で彩色できると述べている。ここで、µは多重グラフの多重度である。 ^{[1]この定理は、1964 年にこれを発表した}Vadim G. Vizingにちなんで名付けられた。

ソ連の数学者ヴァディム・G・ヴィジングによって発見された定理は、1964年にヴィジングがノボシビルスクで研究していたときに発表され、ヴィジングの定理として知られるようになった。^[2]インドの数学者RPグプタは、博士号取得課程（1965-1967年）中にこの定理を独自に発見した。^{[3] [4]}

Δ = 1の場合、グラフG自体はマッチングしており、2 つの辺が隣接しておらず、その辺彩色数は 1 です。つまり、Δ( G ) = 1であるすべてのグラフはクラス 1 です。

Δ = 2の場合、グラフG はパスとサイクルの互いに素な和集合でなければなりません。すべてのサイクルが偶数の場合、各サイクルの周囲で 2 つの色を交互に配置することで、2 辺カラーリングできます。ただし、少なくとも 1 つの奇数サイクルが存在する場合、2 辺カラーリングは不可能です。つまり、Δ = 2のグラフがクラス 1 になるのは、 2 部グラフである場合のみです。

この証明は Diestel (2000) に触発されたものです。

G  = ( V ,  E )を単純な無向グラフとします。辺の数mについて帰納的に進めます。グラフが空の場合、定理は自明に成り立ちます。m  > 0とし、 xy  ∈  EであるすべてのG  −  xyに対して適切な (Δ+1) 辺彩色が存在すると仮定します。

すべてのy  ∈ N( x )に対してc ( xy ) ≠ α であるとき、x  ∈  Vにおいて適切な(Δ+1)辺彩色cに関して色α ∈ {1,...,Δ+1 } が欠落しているといえます。また、xからのα/βパスは、 xでα色の辺から始まり辺の色が交互に変わる（2番目の辺は色β、3番目の辺は色αなど）唯一の最大パスを表し、その長さは0になることがあります。 c がGの適切な(Δ+1)辺彩色である場合、すべての頂点はcに関して欠落した色を持つことに注意してください。

Gの適切な(Δ+1)辺色付けが存在しないと仮定します。これは次のステートメントと同等です。

(1) xy  ∈  E、c をG  −  xyの任意の適切な(Δ+1)辺彩色とし、cに関してxからαが欠落し、yからβが欠落しているとします。このとき、yからのα/βパスはxで終わります。

これは同等です。なぜなら、(1)が成り立たない場合、α/βパス上の色αとβを交換し、 xyの色をαに設定して、cからGの適切な(Δ+1)エッジカラーリングを作成できるからです。逆に、適切な(Δ+1)エッジカラーリングが存在する場合は、xyを削除してカラーリングを制限し、(1)も成り立ちません。

ここで、xy ₀  ∈  E、c _{0 を}G  −  xy ₀の適切な(Δ+1)辺彩色、α をc ₀に関してxに欠けているとします。y ₀ ,..., y _{k を}、すべての0 <  i  ≤  kに対してc ₀ ( xy _i )がy _{i −1}に関してc ₀に欠けているようなxの近傍の最大シーケンスと定義します。

色付けc ₁ ,..., c _kを次のように 定義する。

c _i ( xy _j )= c ₀ ( xy _{j +1} )であり、すべての0 ≤  j  <  iに対して、

c _i ( xy _i )は定義されていません。

それ以外の場合はc _i ( e )= c ₀ ( e )です。

すると、y ₀ ,..., y _kの定義により、c _{i は}G  −  xy _iの適切な(Δ+1)辺色になります。また、 xの欠けている色は、すべての0 ≤  i  ≤  kに対してc _iに関して同じであることに注意してください。

β をc ₀に関してy _kに欠けている色とすると、β は、 0 ≤  i  ≤  kのすべてについて、 c _iに関してy _kにも欠けています。β はxに欠けることはできないことに注意してください。そうでなければ、 c _{k を}簡単に拡張できるため、色βのエッジはすべてのc _jについてxに接続します。 kの最大値から、 c ₀ ( xy _i ) = βとなる1 ≤  i  <  kが存在します。 c ₁、...、c _kの定義から、次の式が成り立ちます。

c ₀ ( xy _i ) =  c _{i −1} ( xy _i ) =  c _k ( xy _{i −1} ) = β

P をy _kからc _kに関するα/βパスとします。 (1) から、P はxで終了する必要があります。しかし、 αはxにないため、色βのエッジで終了する必要があります。したがって、 Pの最後のエッジはy _{i −1} xです。次に、P' をy _{i −1}からc _{i −1}に関するα/βパスとします。P'は一意に決定され、 Pの内側のエッジはc ₀、...、c _kで変更されないため、パスP' はPと同じエッジを逆の順序で使用し、y _{k を}訪れます。 y _kにつながるエッジの色は明らかにαです。しかし、βはy _kにないため、P' はy _kで終了します。これは上記 (1) と矛盾しています。

いくつかの著者は、いくつかのグラフをクラス1またはクラス2に分類する追加条件を提示しているが、完全な分類は提供していない。たとえば、グラフGの最大次数Δの頂点が独立集合を形成する場合、またはより一般的には、この頂点集合の誘導サブグラフがフォレストである場合、 Gはクラス1でなければならない。^[5]

Erdős & Wilson (1977) は、ほぼすべてのグラフがクラス 1 であることを示しました。つまり、すべてのn頂点グラフが等確率であるランダム グラフのErdős–Rényi モデルにおいて、この分布から抽出されたn頂点グラフがクラス 1 である確率を p (n) とすると、nが無限大に近づくにつれてp (n) は 1に近づきます。p ( n ) が1 に収束する速度のより正確な境界については、Frieze ら (1988) を参照してください。

Vizing (1965) は、最大次数が少なくとも 8 の場合、平面グラフはクラス 1 であることを示しました。対照的に、彼は、2 から 5 までの最大次数に対して、クラス 2 の平面グラフが存在することを観察しました。次数 2 の場合、任意の奇数サイクルがそのようなグラフであり、次数 3、4、および 5 の場合、これらのグラフは、1 つのエッジを 2 つの隣接するエッジのパスに置き換えることによって、 プラトン立体から構築できます。

ヴィジングの平面グラフ予想では、ヴィジング (1965) は、最大次数が 6 または 7 であるすべての単純な平面グラフはクラス 1 であると述べており、残りの可能性のあるケースは閉じています。それとは別に、Zhang (2000) と Sanders & Zhao (2001) は、最大次数が 7 であるすべての平面グラフはクラス 1 であることを示し、ヴィジングの平面グラフ予想を部分的に証明しました。したがって、この予想で未解決のまま残っているのは、最大次数が 6 の場合のみです。この予想は、全彩色予想に影響を及ぼします。

プラトン立体の細分化によって構築されるクラス 2 の平面グラフは正則ではありません。このグラフには、次数 2 の頂点と、より高次の頂点があります。平面グラフの頂点彩色に関する4 色定理(Appel & Haken (1976) によって証明) は、すべてのブリッジのない 3 正則平面グラフはクラス 1 であるという主張 (Tait 1880) と同等です。

1969 年、ブランコ・グリュンバウムは、トーラスなどの任意の2 次元有向多様体上に多面体埋め込みを持つすべての 3 正則グラフはクラス 1 でなければならないと予想しました。この文脈では、多面体埋め込みとは、埋め込みのすべての面が位相的に円盤であり、埋め込みの双対グラフが単純で、自己ループや多重隣接がないグラフ埋め込みです。これが正しい場合、これは 4 色定理の一般化になります。これは、球面上に多面体埋め込みを持つ 3 正則グラフはクラス 1 であるというステートメントと同等であると Tait によって示されました。しかし、ココル (2009) は、高種数の有向面上に多面体埋め込みを持つスナークを見つけることで、この予想が誤りであることを示しました。この構成に基づいて、彼はまた、多面体埋め込みグラフがクラス 1 であるかどうかを判断することは NP 完全であることを示しました。^[6]

Misra と Gries (1992) は、グラフのエッジをΔ + 1色で着色する多項式時間アルゴリズムを説明しています。ここで、 Δはグラフの最大次数です。つまり、アルゴリズムはクラス 2 のグラフに最適な色数を使用し、すべてのグラフに必要な色より多くても 1 色多く使用します。彼らのアルゴリズムは、Vizing の定理の最初の証明と同じ戦略に従います。つまり、色付けされていないグラフから始めて、色付けされたエッジの数を 1 つ増やすためにグラフの色付け方法を繰り返し見つけます。

より具体的には、uv が部分的に色付けされたグラフ内の色付けされていない辺であると仮定します。Misra と Gries のアルゴリズムは、uの近傍に有向擬似フォレスト P (各頂点が最大で 1 つの出力辺を持つグラフ)を構築するものとして解釈できます。 uの各近傍pについて、アルゴリズムはpに接続するどの辺でも使用されていない色c を見つけ、辺uq が色cを持つ頂点q (存在する場合)を見つけ、pq をPへの辺として追加します。次の 2 つのケースがあります。

• このようにして構築された疑似フォレストP に、 vから、 Pに出ているエッジがない頂点wへのパスが含まれている場合、 uとw の両方で使用できる色cが存在します。エッジuw を色cで再着色すると、残りのエッジの色をこのパスに沿って 1 ステップシフトできます。パス内の各頂点pについて、エッジup は、パス内のpの後継で以前に使用された色を取得します。これにより、エッジuv を含む新しい着色が実現します。
• 一方、疑似森Pのvから始まるパスがサイクルにつながる場合、w をパスがサイクルに参加するuの隣接ノードとし、 c をエッジuwの色とし、d を頂点uのどのエッジでも使用されていない色とします。その後、ケンペ チェーンで色cとd を交換すると、サイクルが壊れるか、パスがサイクルに参加するエッジが壊れて、前のケースに戻ります。

各頂点で使用されている色と利用可能な色を追跡するためのいくつかの単純なデータ構造を使用すると、Pの構築とアルゴリズムの色付け手順はすべて、O( n ) の時間で実装できます。ここで、n は入力グラフの頂点の数です。これらの手順はm回繰り返す必要があり、繰り返しごとに色付きのエッジの数が 1 つ増えるため、合計時間はO( mn )です。

未発表の技術レポートで、Gabow ら (1985) は、Δ + 1色で色付けする同じ問題に対して、より高速な時間制限を 主張しました。 ${\displaystyle O(m{\sqrt {n}}\log n)}$

Gutin & Toft (2000) と Soifer (2008) の両方で、Vizing は、多重グラフは最大(3/2)Δ色で着色できることを示す Shannon (1949) の定理に動機付けられたと述べています。Vizing の定理は現在では多くのグラフ理論の教科書の標準的な内容となっていますが、Vizing は当初その結果を発表するのに苦労し、それに関する彼の論文は無名のジャーナルであるDiskret. Analizに掲載されています。^[7]

• 頂点彩色と最大次数の関係を示すブルックスの定理

• アペル, K. ;ハーケン, W. (1976)、「すべての平面マップは 4 色に塗り分け可能」、アメリカ数学会誌、82 (5): 711–712、doi : 10.1090/S0002-9904-1976-14122-5、MR  0424602。
• Diestel、Reinhard (2000)、Graph Theory (PDF)、ベルリン、ニューヨーク: Springer-Verlag、pp. 103–104。
• エルデシュ、ポール、ウィルソン、ロビン J. (1977)、「ほとんどすべてのグラフの彩色指数に関する注記」(PDF)、Journal of Combinatorial Theory、シリーズ B、23 (2–3): 255–257、doi : 10.1016/0095-8956(77)90039-9。
• フルニエ、ジャン＝クロード (1973)、「Colorations des arêtes d'ungraphe」、Cahiers du Centre d'Études de Recherche Opérationnelle、15 : 311–314、MR  0349458。
• フリーズ、アラン M. ; ジャクソン、B.; マクダーミッド、CJH;リード、B. (1988)、「エッジカラーリングランダムグラフ」、Journal of Combinatorial Theory、シリーズ B、45 (2): 135–149、doi :10.1016/0095-8956(88)90065-2、MR  0961145。
• Gabow, Harold N. ; Nishizeki, Takao ; Kariv, Oded ; Leven, Daniel ; Terada, Osamu (1985)、グラフの辺彩色アルゴリズム、技術報告書 TRECIS-8501、東北大学。
• グティン、グレゴリー、トフト、ビャルネ（2000年12月）「ヴァディム・G・ヴィジング氏へのインタビュー」（PDF）、ヨーロッパ数学会ニュースレター、38：22-23。
• ココル、マーティン (2009)、「有向面におけるスナークの多面体埋め込み」、アメリカ数学会紀要、第 137 巻、1613 ～ 1619 ページ。
• Kochol, Martin (2010)、「有向面への多面体埋め込みを持つ立方グラフのクラスにおける 3 辺彩色の複雑性」、離散応用数学、158 (16): 1856–1860、doi : 10.1016/j.dam.2010.06.019、MR  2679785。
• ミスラ、J.;グリース、デイビッド(1992)、「ビジングの定理の構成的証明」、情報処理レター、41 (3): 131–133、doi :10.1016/0020-0190(92)90041-S。
• サンダース、ダニエル P. ; チャオ、ユエ (2001)、「最大次数 7 の平面グラフはクラス I である」、組合せ理論ジャーナル、シリーズ B、83 (2): 201–212、doi : 10.1006/jctb.2001.2047。
• シャノン、クロード E. (1949)、「ネットワークの線の色付けに関する定理」、J. Math. Physics、28 (1–4): 148–151、doi :10.1002/sapm1949281148、MR  0030203。
• ソイファー、アレクサンダー（2008）、数学ぬり絵本、シュプリンガー・フェアラーク、pp. 136-137、ISBN 978-0-387-74640-1。
• テイト、PG (1880)、「地図の色彩に関する考察」、Proc. R. Soc. Edinburgh、10 : 729、doi :10.1017/S0370164600044643。
• Vizing, VG (1964)、「 pグラフの彩度クラスの推定について」、Diskret. Analiz.、3 : 25–30、MR  0180505。
• Vizing, VG (1965)、「与えられた彩色クラスを持つ臨界グラフ」、Metody Diskret. Analiz.、5 : 9–17（ロシア語）
• 張 立民 (2000)、「最大次数 7 のすべての平面グラフはクラス 1 である」、グラフと組合せ論、16 (4): 467–495、doi :10.1007/s003730070009、S2CID  10945647。

• PlanetMathでの Vizing の定理の証明。