オーバーフルグラフ

このグラフは、グラフの最大次数とグラフ内の頂点数（次数）の積を2で割って切り捨てた値よりも大きいため、オーバーフルです。この場合、22÷ 20です。${\displaystyle >}$

数学における未解決問題

予想:グラフGがクラス 2 である場合、かつ、それがオーバーフル サブグラフ S を持ち、その場合のみ、 となります。${\displaystyle \Delta (G)>n/3}$ ${\displaystyle \displaystyle \デルタ (G)=\デルタ (S)}$

数学におけるさらなる未解決問題

グラフ理論において、オーバーフルグラフとは、グラフのサイズが最大次数と位数の半分の積（​​床面積）よりも大きいグラフのことである。つまり、はGのサイズ、はGの最大次数、 はGの位数である。オーバーフルサブグラフ（オーバーフルグラフでありながらサブグラフであるグラフ）の概念は、この概念に即している。グラフGのオーバーフルサブグラフSのより厳密な定義は、を必要とする。 ${\displaystyle |E|>\Delta (G)\lfloor |V|/2\rfloor }$ ${\displaystyle |E|}$ ${\displaystyle \displaystyle \デルタ(G)}$ ${\displaystyle |V|}$ ${\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. となるオーバーフルサブグラフSを持つグラフGは、クラス 2 です。${\displaystyle \displaystyle \デルタ (G)=\デルタ (S)}$

過剰な推測

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

グラフGがクラス 2 となるのは、それがオーバーフル サブグラフ S を持ち、その場合のみです。${\displaystyle \Delta (G)>n/3}$ ${\displaystyle \displaystyle \デルタ (G)=\デルタ (S)}$

この予想が正しいとすれば、1因数分解予想を含むグラフ理論において多くの意味を持つことになる。^{[ 2 ]}

アルゴリズム

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

参考文献

1. Chetwynd, AG; Hilton, AJW (1986)、「最大次数を持つ3つの頂点を持つスターマルチグラフ」(PDF)、ケンブリッジ哲学協会数学紀要、100 (2): 303– 317、Bibcode : 1986MPCPS.100..303C、doi : 10.1017/S030500410006610X、MR  0848854。
2. Chetwynd, AG; Hilton, AJW (1989)、「高次正則グラフの1-因数分解—改良された境界」、離散数学、75 ( 1–3 ): 103– 112、doi : 10.1016/0012-365X(89)90082-4、MR 1001390 。
3. Niessen, Thomas (2001)、「大きな最大次数を持つグラフにおけるオーバーフルサブグラフの見つけ方 II」、Electronic Journal of Combinatorics、8 (1)、研究論​​文7、MR 1814514 。