Hajós の構成

righ1113さんに教えてもらった Hajós construction を読んでみました。Graph Theory - Reinhard Diestel の 5.2 Colouring vertices にあります。

• Reinhard Diestel　Graph Theory　Electronic Edition 2005　© Springer-Verlag Heidelberg, New York 1997, 2000, 2005
• Graph Theory - Reinhard Diestel
  • Graph Theory 5th Edition - Reinhard Diestel (Free preview)
• Hajós construction　Wikipedia

これらには、だいたい以下のようなことが書かれています。

グラフが k-constructible (or Hajós-k-constructible) であるとは、次のように再帰的に定義される。

1. k-完全グラフ は k-constructible である。
2. G が k-constructible であるならば、G で隣接していない頂点x,y を合併してできる グラフも k-constructible である。正確には G に 辺xy を付け加えた後、xy を縮約する。記号では (G + xy)/xy
3. G₁, G₂ の両方が k-constructible であるとする。頂点x, y₁, y₂ があり、 G₁, G₂ の共通部分が 頂点x のみで、xy₁ ∈ E(G₁) and xy₂ ∈ E(G₂) とする。 すると (G₁ ∪ G₂) − xy₁ − xy₂ + y₁y₂ は k-constructible である。

k-constructible なグラフは彩色にk-色またはそれ以上の色を必要とする。(i)の k-完全グラフは自明に k-色を必要とする。(ii)では x と y を同じ色にするという制約を増やすのと同じ意味であって、彩色に必要な色は増えることはあっても、減ることはない。(iii)では、x と y₁ を異なる色にすると、これは xy₁ を戻すのと同じ意味となり、G₁の部分の彩色にk色以上を必要とする。x と y₂ を異なる色にすると xy₂ を戻すのと同じ意味となり、G₂の部分の彩色にk色以上を必要とする。x と y₁ を同じ色とし、かつx と y₂ を同じ色とした場合は y₁y₂ の両端の色が同じとなり彩色にならない。したがって、彩色には少なくとも k色が必要になる。そしてこの逆も成立する。

定理 5.2.6. (Hajós 1961)　G をグラフとし、k を自然数とする。χ(G) ≥ k となるのは、G が k-constructible なグラフを含むとき、かつそのときに限る。

この後に証明があるのですが、その中にある構成法を具体例で試すことにします。

次のグラフGの彩色には４色が必要十分です。（4-critical graph になっています）

実は x, y₁, 2 の３頂点に着目すれば、もう少し簡単になります。ですが Hajós の構成法の説明のためこのようにしました。

y₁y₂ は G に含まれています。xy₁ と xy₂ は G に含まれていません。G に xy₁ を付け加えたうえで、xy₁ を含む 4-constructible な部分グラフを探して H₁ とします。同様に、G に xy₂ を付け加えたうえで、xy₂ を含む 4-constructible な部分グラフを H₂ とします。

H₂ のコピーをつくり H'₂ とします。x 以外の頂点は 1', y'₁ のようにします。

これで (iii) の要件を満たすようになりました。xy₁ と xy'₂ を取り除き、y₁y'₂ を付け加えます。

(ii)を使って、3' と 3 を結ぶ辺を付け加えて縮約し、4' と 4 を結ぶ辺を付け加えて縮約し、y'₁ と y₁ を結ぶ辺を付け加えて縮約します。1', 2', y'₂ については、名前を変えて 1, 2, y₂ とするだけです。その結果、G が出来上がります。G も 4-constructible であることが証明できました。（本当は H₂ も 4-constructible であることを証明しなければなりませんが）

定理 5.2.6 の証明は背理法でおこなわれ、上記の構成方法が使われています。勝手に補った証明を書きます。

G を χ(G) ≥ k である（彩色に k 色以上必要な）グラフとする。G は k-constructible な部分グラフを含むことを示す。そうではないと仮定する。k ≥ 3 としてよい（G は辺を持たなくてはならないから k = 2 だと 自明）。もし必要なら辺を付け足すことによって、G を k-constructible な部分グラフを持たない edge-maximal なグラフにすることができる（辺を付け足していけば、いつかは完全グラフになってしまいますから）。すると G は任意の自然数 r において完全 r 部グラフではない。そうではなく、完全 r 部グラフであったとすると r ≥ χ(G) ≥ k より、r ≥ k となり、G は k-constructible である完全グラフ K^k を含むことになる。

G が完全多部グラフではないことより、非隣接は V(G) 上の同値関係ではない。（非隣接が V(G) 上の同値関係であるとは、xy₁ ∉ E(G) かつ xy₂ ∉ E(G) ならば y₁y₂ ∉ E(G) となっていること。）それで、y₁x, xy₂ ∉ E(G) しかし y₁y₂ ∈ E(G) となるような 頂点 y₁, x, y₂ がある。G が k-constructible な部分グラフを持たないという条件での edge-maximal なグラフであることから、 G + xy_i (i = 1, 2) それぞれに xy_i を含む k-constructible な部分グラフ Hi がある。

完全多部グラフなら、非隣接は同じ partition どうしの頂点にしかなく、同値関係になっている。逆に非隣接が同値関係になっているグラフは完全多部グラフになっていることを、強欲アルゴリズムで証明します。

まず partition P1 を用意して x を入れます。もし x に隣接していない頂点があれば、それも P1 に入れます。さらに x に隣接していない頂点があればそれも P1 に入れます。非隣接が同値関係なので、すでに P1 に入っているどの頂点とも隣接していないはずです。これを繰り返すと、P1 の頂点はどれも、P1 に含まれていない頂点と隣接しているようになります。まだ他に頂点があれば、P2 を用意して同様に繰り返します。これで完全多部グラフであることがわかります。

G が完全多部グラフでないなら xy₁ ∉ E(G) かつ xy₂ ∉ E(G) であるような３頂点 x, y1, y2 があることも証明しなければなりません。２頂点以下のグラフでは無意味なので、３個以上の頂点があるものとします。

xy₁ ∉ E(G) かつ xy₂ ∉ E(G) であるような３頂点 x, y1, y2 が存在しないものとします。グラフG は r-部グラフであるとします。ただし r はできるだけ小さい自然数となるようにします。各 partition は２個より多くの頂点を含まないはずです。２個の頂点を含む partetion の頂点は、他の partition の頂点すべてに隣接していなくてはなりません。r の最小性から、１個の頂点しか含まない pertition の頂点は他の１個の頂点を含む pertition の頂点すべてに隣接していなくてはなりません。ゆえに G は完全 r 部グラフです。

y₁x, xy₂ ∉ E(G) しかし y₁y₂ ∈ E(G) となるような 頂点 y₁, x, y₂ が G にあることが示され、その３点を使って上記の方法でグラフが再構成され、矛盾が示されます。

おおよそのことは理解できたと思うのですが、気になるのは (iii) の条件のきびしさです。G₁ と G₂ の共通部分として１つの頂点しか許さないところです。もし彩色に k色必要な完全グラフではないグラフが、"かならず" (iii)の条件で分解できるならば G₂ の内部に x から y₂ へのパスがあることになります。このパスを縮約してしまえば、より小さい k色必要なグラフとなり、Hadwiger予想が成立することになります。Hajós予想にも近づくことになります。ただの想像ですが、こうしたことが背景にあるものと思われます。

それに k 完全グラフの拡張ともいえる 完全 k 部グラフに還元する論法も面白く、四色定理証明の見込みがあると感じたかもしれません。

これに対して私の方法は、恒真式で書くからそれを確かめるにはブール代数のルールで自由にやってくれ、という感じです。普通の数学の問題でも方程式で表してしまえば、それを解くのは好きな方法でかまわないのと同様です。

ブール代数ルールで構成してみます。

Home