アルバートソン予想
グラフの色分けと交差の関係
数学における未解決問題
完全グラフは 、同じ彩色数を持つグラフ間で可能な限り最小の交差数を持ちますか?
数学におけるさらなる未解決問題
3つの交差で描かれた完全グラフ。6色を必要とするグラフの中で交差数が最小である。 K 6 {\displaystyle K_{6}}

組合せ 数学において、アルバートソン予想はグラフの交差数と彩色数との間の証明されていない関係である。これはスミス大学教授のマイケル・O・アルバートソンにちなんで名付けられ、彼はこれを予想として2007年に述べた。[1]これはグラフ彩色理論における彼の多くの予想の1つである。[2]この予想は、色を必要とするすべてのグラフの中で、完全グラフは交差数が最小のグラフであると述べている。同様に、 よりも少ない交差でグラフを描くことができる場合、この予想によれば、そのグラフは よりも少ない色で彩色できる。 n {\displaystyle n} K n {\displaystyle K_{n}} K n {\displaystyle K_{n}} n {\displaystyle n}

最小交差数の推定式

交差数が有限であるグラフは、彩色数も有限であることを示すのは簡単です。すべての交差辺の端点に異なる色を割り当て、残りの平面グラフを4色に塗り分ければよいのです。アルバートソンの予想は、交差数と彩色の間のこの定性的な関係をより正確な定量的な関係に置き換えます。具体的には、リチャード・K・ガイ(1972)の別の予想 では、完全グラフの交差数は K n {\displaystyle K_{n}}

cr （ K n ） ＝ 1 4 ⌊ n 2 ⌋ ⌊ n − 1 2 ⌋ ⌊ n − 2 2 ⌋ ⌊ n − 3 2 ⌋ 。 {\displaystyle {\textrm {cr}}(K_{n})={\frac {1}{4}}{\biggl \lfloor }{\frac {n}{2}}{\biggr \rfloor }\left\lfloor {\frac {n-1}{2}}\right\rfloor \left\lfloor {\frac {n-2}{2}}\right\rfloor \left\lfloor {\frac {n-3}{2}}\right\rfloor .}

頂点を二つの同心円に配置することで、これほど多くの交差を持つ完全グラフを描く方法は知られている。しかし、より少ない交差を持つより良い描画方法が存在するかどうかは未知である。したがって、アルバートソン予想の強化された定式化は、すべての- 彩色グラフの交差数が少なくともこの式の右辺と同じであるというものである。[3]この強化された予想は、ガイ予想とアルバートソン予想の両方が成り立つ場合にのみ成り立つ。 n {\displaystyle n}

漸近境界

M. Schaefer によって証明されたこの予想の弱い形式[3]では、彩色数 を持つすべてのグラフには交差数（大オメガ記法を使用）がある、あるいはそれと同等に、交差数 を持つすべてのグラフには彩色数 があると述べています。Albertson、Cranston、Fox (2009) は、すべての極小-彩色グラフの最小次数が少なくとも である という事実（そうでなければ貪欲な彩色でより少ない色を使用するため）と、を持つすべてのグラフには交差数 があるという交差数不等式を組み合わせることで、これらの境界の簡単な証明を発表しました。同じ推論を使用して、彼らは、彩色数に関する Albertson の予想に対する反例（存在する場合）は、頂点の数が より少なくなければならないことを示しています。 n {\displaystyle n} Ω （ n 4 ） {\displaystyle \オメガ (n^{4})} け {\displaystyle k} お （ け 1 / 4 ） {\displaystyle O(k^{1/4})} n {\displaystyle n} n − 1 {\displaystyle n-1} G ＝ （ V 、 E ） {\displaystyle G=(V,E)} | E | / | V | ≥ 4 {\displaystyle |E|/|V|\geq 4} Ω （ | E | 3 / | V | 2 ） {\displaystyle \Omega (|E|^{3}/|V|^{2})} n {\displaystyle n} 4 n {\displaystyle 4n}

特殊なケース

アルバートソン予想はに対して空虚に真である。これらの場合、の交差数は 0 なので、予想は-彩色グラフの交差数が 0 以上であることのみを述べており、これはすべてのグラフに当てはまる。アルバートソン予想の場合は、 4 色定理と同等であり、任意の平面グラフは 4 色以下で彩色できる。 の 1 回の交差よりも少ない交差を必要とするグラフは平面グラフのみであり、予想はこれらすべてが最大でも 4 彩色であるべきであることを意味する。複数の著者グループの努力により、予想は現在ではすべての に対して成り立つことがわかっている。[4]すべての整数 に対して、ルイスとリヒターは、完全グラフの細分を含まないが、交差数が少なくとも の交差数を持つ-色臨界グラフの族を提示した。[5] n ≤ 4 {\displaystyle n\leq 4} K n {\displaystyle K_{n}} n {\displaystyle n} n ＝ 5 {\displaystyle n=5} K 5 {\displaystyle K_{5}} n ≤ 18 {\displaystyle n\leq 18} c ≥ 6 {\displaystyle c\geq 6} （ c + 1 ） {\displaystyle (c+1)} K c + 1 {\displaystyle K_{c+1}} K c + 1 {\displaystyle K_{c+1}}

また、これはハドヴィガー予想とも関連がある。ハドヴィガー予想は、グラフの彩色数とマイナーグラフとしての大きなクリークの存在との関係に関する、組合せ論における重要な未解決問題である。 [6]ジェルジ・ハヨシュによって述べられたハドヴィガー予想の変種は、すべての-彩色グラフにはの細分が含まれるというものである。もしこれが真であれば、グラフ全体の交差数はそのどの細分においても交差数以上であるため、アルバートソン予想が導かれる。しかし、ハヨシュ予想に対する反例が現在では知られているため[7]、この関連はアルバートソン予想の証明の道筋を提供しない。 n {\displaystyle n} K n {\displaystyle K_{n}}

注記

  1. ^ Albertson、Cranston、Fox (2009) によると、この予想は2007 年 10 月にシカゴで開催されたアメリカ数学会の特別セッションで Albertson によってなされた。
  2. ^ ハッチンソン、ジョーン・P.（2009年6月19日）、マイケル・O・アルバートソンを偲んで（1946-2009）：グラフ理論における彼の傑出した予想と疑問のコレクション（PDF）、SIAM離散数学活動グループ。
  3. ^ ab Albertson、Cranston、Fox (2009)。
  4. ^ オポロフスキーとチャオ (2009);アルバートソン、クランストン、フォックス (2009);バラートとトート (2010);アッカーマン（2019）。
  5. ^ Luiz & Richter (2014).
  6. ^ Barát & Tóth (2010).
  7. ^ キャットリン (1979);エルデシュとファイトロヴィチ (1981)。

参考文献

  • アッカーマン、エヤル（2019）、「辺あたり最大4つの交差を持つ位相グラフについて」、計算幾何学、85：101574、31、arXiv：1509.01932、doi：10.1016/j.comgeo.2019.101574、MR  4010251、S2CID  16847443
  • Albertson, Michael O.; Cranston, Daniel W.; Fox, Jacob (2009)「Colorings, crossings, and cliques」（PDF） , Electronic Journal of Combinatorics , 16 : R45, arXiv : 1006.3783 , Bibcode :2010arXiv1006.3783A, doi :10.37236/134, S2CID  8837711。
  • バラート、ヤーノス。 Tóth、Géza (2010)、「Towards the Albertson Conjecture」、Electronic Journal of Combinatorics、17 (1): R73、arXiv : 0909.0413、Bibcode :2009arXiv0909.0413B、doi :10.37236/345、S2CID  14640959。
  • Catlin, PA (1979)、「ハヨスのグラフ彩色予想：バリエーションと反例」、Journal of Combinatorial Theory、シリーズB、26 (2): 268– 274、doi : 10.1016/0095-8956(79)90062-5。
  • ポール・エルデシュ; Fajtlowicz、Siemion (1981)、「ハジョスの予想について」、Combinatorica、1 (2): 141–143、doi :10.1007/BF02579269、S2CID  1266711。
  • Guy, Richard K. (1972)、「グラフの交差数」、Alavi, Y.、Lick, DR、White, AT (編)、『グラフ理論と応用：西ミシガン大学会議録』（1972年5月10～13日、ミシガン州カラマズー）、ニューヨーク：Springer-Verlag、pp.  111～ 124Albertson、Cranston、Fox（2009）による引用。
  • Oporowski, B.; Zhao, D. (2009)、「交差によるグラフの色付け」、離散数学、309 (9): 2948– 2951、arXiv : math/0501427、doi :10.1016/j.disc.2008.07.040、S2CID  16497175。
  • Luiz, Atílio; Richter, Bruce (2014)、「BarátとTóthの予想に関する考察」、Electronic Journal of Combinatorics、21 (1): P1.57、doi : 10.37236/3396。
「https://en.wikipedia.org/w/index.php?title=アルバートソンの予想&oldid=1170366158」より取得