グラフが満杯です

数学における未解決問題

予想:グラフGは${\displaystyle \Delta (G)>n/3}$がクラス 2 であるのは、以下の条件を満たすオーバーフル部分グラフ S を持つ場合に限る。${\displaystyle \displaystyle \デルタ (G)=\デルタ (S)}$。

数学における未解決問題

グラフ理論において、オーバーフルグラフとは、その最大次数と次数を切り捨てた半分の積よりも大きいサイズのグラフのことである。${\displaystyle |E|>\Delta (G)\lfloor |V|/2\rfloor }$どこ${\displaystyle |E|}$Gのサイズは、${\displaystyle \displaystyle \デルタ(G)}$はGの最大次数であり、${\displaystyle |V|}$はGの次数である。部分グラフである部分グラフである部分グラフ、つまり部分グラフである部分グラフの概念がすぐに導かれる。グラフGの部分グラフSのより厳密な別の定義には、次のことが必要である。${\displaystyle \displaystyle \デルタ (G)=\デルタ (S)}$。

長さが 3 以上の奇数サイクル グラフはすべてオーバーフルです。次数 (2) と長さの半分 (切り捨て) の積は、サイクル内のエッジの数より 1 少なくなります。より一般的には、奇数を持つすべての正則グラフはオーバーフルです。${\displaystyle n}$頂点の数がオーバーフルです。エッジの数、${\displaystyle \Delta n/2}$（どこ${\displaystyle \Delta }$（その次数）は、より大きい。${\displaystyle \Delta \lfloor n/2\rfloor }$。

過剰グラフのいくつかの特性：

1. グラフが過剰に詰まっている場合、グラフの次数は奇数になります。
2. 過剰グラフはクラス2です。つまり、任意のエッジ彩色において、少なくともΔ + 1色が必要です。
3. グラフGには、以下の条件を満たすオーバーフル部分グラフS が存在する。${\displaystyle \displaystyle \デルタ (G)=\デルタ (S)}$はクラス2です。

1986年、アマンダ・チェトウィンドとアンソニー・ヒルトンは、現在オーバーフル予想として知られる以下の予想を提唱した。^{[ 1 ]}

グラフGは${\displaystyle \Delta (G)>n/3}$がクラス 2 であるのは、以下の条件を満たすオーバーフル部分グラフ S を持つ場合に限る。${\displaystyle \displaystyle \デルタ (G)=\デルタ (S)}$。

この予想が正しければ、1-因数分解予想を含むグラフ理論に多くの影響を与えるだろう。^{[ 2 ]}

グラフの場合${\displaystyle \Delta \geq n/3}$の場合、誘導されるオーバーフル部分グラフは最大で 3 つであり、オーバーフル部分グラフを多項式時間で見つけることが可能です。${\displaystyle \Delta \geq n/2}$誘導されるオーバーフル部分グラフは最大で 1 つしか存在せず、線形時間でそれを見つけることが可能です。^{[ 3 ]}