強い亜線形セパレーターを持つグラフクラスの積構造

我々は、強い亜線形セパレーターを持つ遺伝的グラフクラスの積構造を調査します。そのようなクラスを、星グラフと強いサイズの完全グラフの強い積の部分グラフとして特徴付けます。より正確な結果として、任意の遺伝的グラフクラス𝒢がO(n^{1-ϵ})セパレーターを持つ場合、任意の固定されたδ∈(0,ϵ)に対して、𝒢内の任意のn頂点グラフは、制約された木深さを持つグラフHの強い積の部分グラフであり、サイズO(n^{1-ϵ+δ})の完全グラフです。この結果は、Hに木深さO(loglogn)を許可したとき、δ=0の場合でも成り立ちます。加えて、格子グラフに対する古典的な等周性不等式の拡張を利用して、我々の結果におけるδへの依存性と、上記のtd(H)∈O(loglogn)の上限が双方とも最適であることを示します。n頂点の木幅が制約されたグラフは、木深さtを持つグラフとの積と、サイズO(n^{1/t})の完全グラフの部分グラフであることを証明し、これは最適です。最後に、任意の遺伝的グラフクラス𝒢がO(n^{1-ϵ})セパレーターを持つ場合、𝒢内の任意のn頂点グラフは、制約された木幅を持つグラフHの強い積の部分グラフであり、サイズO(n^{1-ϵ})の完全グラフを持つという予想を調査します。これは、興味深いさまざまなクラス𝒢に対して証明します.