アルバートソン予想

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

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

${\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 .}$

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

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

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

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

• アッカーマン、エヤル (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)、「Hajós のグラフ着色予想: バリエーションと反例」、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。