ハドヴィガー予想（グラフ理論）

数学における未解決の問題:

彩色数を 持つすべてのグラフには、マイナーとして-頂点完全グラフがありますか?${\displaystyle k}$${\displaystyle k}$

（数学における未解決の問題がさらに増える）

グラフ理論において、ハドヴィガー予想は、がループを持たず、マイナーを持たない場合、その彩色数はを満たすと述べている。これは に対して真であることが知られている。この予想は4 色定理の一般化であり、この分野における最も重要かつ困難な未解決問題の 1 つであると考えられている。 ${\displaystyle G}$${\displaystyle K_{t}}$ ${\displaystyle \chi (G)<t}$${\displaystyle 1\leq t\leq 6}$

より詳しくは、無向グラフのすべての適切な彩色に 色以上が使用される場合、各サブグラフが辺によって他の各サブグラフに接続されているの互いに素な連結サブグラフを見つけることができます。これらの各サブグラフ内の辺を縮小して、各サブグラフが単一の頂点に縮小されるようにすると、のマイナーとして頂点上の完全グラフが生成されます。 ${\displaystyle G}$${\displaystyle k}$${\displaystyle k}$ ${\displaystyle G}$ ${\displaystyle K_{k}}$${\displaystyle k}$ ${\displaystyle G}$

この予想は、 4色問題の広範囲にわたる一般化であり、1943年にヒューゴ・ハドヴィガーによってなされましたが、現在も未解決です。^[1] Bollobás、Catlin、Erdős（1980）は、これを「グラフ理論における最も深い未解決問題の一つ」と呼んでいます。^[2]

ハドヴィガー予想の同等の形式（上記の形式の逆否定）は、グラフを完全グラフにする一連の辺収縮（それぞれが、ある辺の 2 つの端点を 1 つの超頂点にマージする）が存在しない場合、グラフには色による頂点彩色が必ず存在するというものです。 ${\displaystyle G}$${\displaystyle K_{k}}$${\displaystyle G}$${\displaystyle k-1}$

任意のグラフの極小 -彩色において、彩色の各色クラスを単一の頂点に縮約すると、完全なグラフが生成されます。ただし、この縮約プロセスでは、同じ色クラスの任意の 2 つの頂点間に辺が (定義により) 存在しないため、マイナー グラフは生成されず、縮約は辺縮約 (マイナー グラフに必要な) ではありません。Hadwigerの予想では、頂点の集合を単一の頂点に適切に縮約して、すべての縮約集合が接続されるように 完全なグラフ を生成する別の方法が存在するとされています。${\displaystyle k}$${\displaystyle G}$${\displaystyle K_{k}}$${\displaystyle G}$${\displaystyle K_{k}}$

が、 のグラフのすべてのマイナーが - 色にできるという性質を持つグラフの族を表す場合、ロバートソン・シーモア定理から、 は禁制マイナーの有限集合によって特徴付けられることがわかります。ハドヴィガーの予想は、この集合が単一の禁制マイナーで構成されているというものです。${\displaystyle {\mathcal {F}}_{k}}$${\displaystyle {\mathcal {F}}_{k}}$${\displaystyle (k-1)}$${\displaystyle {\mathcal {F}}_{k}}$${\displaystyle K_{k}}$

グラフのハドヴィガー数は 、のマイナーである（または同等にの辺を縮約することによって得られる）最大の完全グラフのサイズです。の縮約クリーク数としても知られています。^[2]ハドヴィガー予想は、が の彩色数を表す単純な代数形式で表すことができます。${\displaystyle h(G)}$${\displaystyle G}$${\displaystyle k}$${\displaystyle K_{k}}$${\displaystyle G}$${\displaystyle G}$ ${\displaystyle G}$${\displaystyle \chi (G)\leq h(G)}$${\displaystyle \chi (G)}$ ${\displaystyle G}$

この場合は自明です。グラフに複数の色が必要なのは、グラフに辺があり、その辺自体がマイナーである場合のみです。この場合も簡単です。3 色が必要なグラフは非二部グラフであり、すべての非二部グラフには奇数サイクルがあり、これは 3 サイクル、つまりマイナーに縮約できます。 ${\displaystyle k=2}$${\displaystyle K_{2}}$${\displaystyle k=3}$${\displaystyle K_{3}}$

この予想を発表した同じ論文で、ハドヴィガーはについてその真偽を証明しました。${\displaystyle k=4}$マイナーグラフのないグラフは、直列並列グラフとそのサブグラフです。このタイプの各グラフには、最大で 2 つの接続辺を持つ頂点があります。このようなグラフを 3 色にするには、そのような頂点を 1 つ削除し、残りのグラフを再帰的に色付けしてから、削除した頂点を戻して色付けします。削除した頂点には最大で 2 つの辺しかないため、頂点を戻したときには、常に 3 色のうちの 1 つを使用して色付けできます。 ${\displaystyle K_{4}}$

に対する予想が正しいことは、四色定理を意味します。なぜなら、予想が正しい場合、5 色以上を必要とするすべてのグラフにはマイナーがあり、(ワグナーの定理により) 非平面グラフになるからです。 クラウス・ワグナーは1937 年に、このケースは実際には四色定理と同等であることを証明したため、今ではこれが正しいことがわかっています。ワグナーが示したように、マイナーを持たないすべてのグラフは、クリーク和を介して平面または 8 頂点のメビウス ラダーのいずれかの断片に分解でき、これらの断片はそれぞれ互いに独立して 4 色にすることができます。そのため、マイナーのないグラフの 4 色可能性は、平面断片のそれぞれが 4 色に色付けされることからわかります。 ${\displaystyle k=5}$${\displaystyle K_{5}}$${\displaystyle k=5}$${\displaystyle K_{5}}$${\displaystyle K_{5}}$

Robertson、Seymour、Thomas (1993) は、についても 4 色定理を用いて予想を証明しました。この証明を記した彼らの論文は、1994 年の${\displaystyle k=6}$Fulkerson Prize を受賞しました。彼らの証明から、平面グラフの 3 次元類似体であるリンクなしで埋め込み可能なグラフの彩色数は最大で 5 であることがわかります。^[3]この結果により、予想はについては正しいことがわかっていますが、${\displaystyle k\leq 6}$すべてのについては未解決のままです。${\displaystyle k>6}$

については、いくつかの部分的な結果がわかっています。すべての7色グラフには、マイナーまたはマイナーとマイナーの両方が含まれている必要があります。^[4]${\displaystyle k=7}$${\displaystyle K_{7}}$${\displaystyle K_{4,4}}$${\displaystyle K_{3,5}}$

すべてのグラフには最大で接続辺を持つ頂点があり、 ^[5]このことから、この低次数の頂点を削除し、残りのグラフを着色し、削除した頂点を追加して着色する貪欲着色アルゴリズムは、指定されたグラフを色で着色することになります。 ${\displaystyle G}$${\textstyle O{\bigl (}h(G){\sqrt {\log h(G)}}{\bigr )}}$${\textstyle O{\bigl (}h(G){\sqrt {\log h(G)}}{\bigr )}}$

1980年代に、アレクサンダー・V・コストカ^[6]とアンドリュー・トーマスン^[7]は、マイナーグラフを持たないすべてのグラフは平均次数を持ち、したがって色を使って色付けできることを独立に証明しました。この境界に対する一連の改良により、マイナーグラフを持たないグラフの-色可能性の証明が生まれました。^[8]${\displaystyle K_{k}}$${\textstyle O(k{\sqrt {\log k}})}$${\textstyle O(k{\sqrt {\log k}})}$${\displaystyle O(k\log \log k)}$${\displaystyle K_{k}}$

ジェルジ・ハヨシュは、ハドヴィガーの予想は小区分ではなく区分に強化できると予想した。つまり、彩色数を持つすべてのグラフには、完全グラフの区分が含まれる、というものである。ハヨシュの予想はに対しては成り立つが、 Catlin (1979) はに対してこの強化された予想の反例を発見した。および の場合は未解決のままである。^[9]エルデシュとファイトロヴィッチ (1981) は、ハヨシュの予想はランダムグラフに対しては完全には当てはまらないことを観察した。つまり、任意の に対して、頂点数 が無限大に近づく極限では、ランダム-頂点グラフが彩色数を持ち、その最大クリーク区分に頂点が含まれる確率は 1 に近づく。この文脈では、ランダムな-頂点グラフのハドヴィガー数がその彩色数以上になる確率も1に近づくことに注目すべきであり、そのためハドヴィガー予想は高い確率でランダムグラフに対して成立する。より正確には、ハドヴィガー数は高い確率で に比例する。[ ^2]${\displaystyle k}$${\displaystyle K_{k}}$${\displaystyle k\leq 4}$${\displaystyle k\geq 7}$${\displaystyle k=5}$${\displaystyle k=6}$${\displaystyle \varepsilon >0}$${\displaystyle n}$${\displaystyle n}$${\displaystyle \geq ({\tfrac {1}{2}}-\varepsilon )n/\log _{2}n}$${\textstyle O({\sqrt {n}})}$${\displaystyle n}$${\textstyle n/{\sqrt {\log n}}}$

Borowiecki (1993) は、Hadwiger の予想をリスト彩色に拡張できるかどうかを問いました。に対して、${\displaystyle k\leq 4}$リスト彩色数 を持つすべてのグラフには、-頂点クリークマイナーがあります。しかし、平面グラフの最大リスト彩色数は 4 ではなく 5 なので、この拡張は-マイナーのないグラフに対してすでに失敗しています。^[10]より一般的には、すべてのに対して、 Hadwiger 数が で、リスト彩色数が であるグラフが存在します。^[11]${\displaystyle k}$${\displaystyle k}$${\displaystyle K_{5}}$${\displaystyle t\geq 1}$${\displaystyle 3t+1}$${\displaystyle 4t+1}$

ジェラーズとシーモアは、彩色数を持つすべてのグラフは、奇数マイナーとして完全グラフを持つと予想した。そのような構造は、 の頂点分離した部分木の族として表すことができ、各部分木は2色で、各部分木ペアは単色の辺で接続されている。奇数マイナーを持たないグラフは必ずしもスパースではないが、標準的なハドヴィガー予想と同様の上限がそれらにも成り立つ。つまり、奇数マイナーを持たないグラフは彩色数 を持つ。^[12]${\displaystyle G}$${\displaystyle k}$${\displaystyle K_{k}}$${\displaystyle k}$${\displaystyle G}$${\displaystyle K_{k}}$${\displaystyle K_{k}}$${\textstyle \chi (G)=O{\bigl (}k{\sqrt {\log k}}{\bigr )}}$

に追加の条件を課すことで、よりも大きなマイナーグラフの存在を証明できる可能性があります。1つの例は、スナーク定理です。これは、任意の辺彩色で4色を必要とするすべての立方グラフには、ピーターセングラフがマイナーグラフとして存在するという定理で、 WTタットによって予想され、2001年にロバートソン、サンダース、シーモア、トーマスによって証明されたことが発表されました。^[13]${\displaystyle G}$${\displaystyle K_{k}}$