グラフのSeparatorについて2

A separator theorem for minor-closed classes を読むと、minor-closedなグラフは $o(n)$ のseparatorを持つのでは？という話がされている。この論文では実際に、 $K_t$ をminorとして含まないようなグラフについて、 $O(t\sqrt{n})$ のseparatorを持つことを証明している。

したがって、bounded degreeのグラフは $O(d\sqrt{n})$ のseparator持つことがわかった。

考察として、 $K_t$ には辺が $O(t^2)$ 本含まれるため、辺の数が $O(n)$ のグラフだと、たかだか $O(\sqrt{n})$ な $t$ について $K_t$ しか含むことができない。

このままの条件だと、やはりほとんどすべてのbounded average degreeなグラフが $o(n)$ のseparatorを持つことができないことになってしまうが、 $o(\sqrt{n})$ な $t$ について $K_t$ しか含めないようなグラフは $o(\sqrt{n})$ のsepartorを持てることになる。