Subgraph-closed classes with strongly sublinear separators have subexponential expansion

About 12 years old · traced to

Let G{\cal G} be a subgraph-closed class of graphs. Suppose that G{\cal G} has strongly sublinear separators. Subexponential expansion conjecture. The expansion of G{\cal G} is subexponential; that is, there exists a function ff with log⁡f(k)=o(k)\log f(k)=o(k) such that the expansion of G{\cal G} is bounded by ff. This would remove the bounded-maximum-degree hypothesis from the paper's theorem and give an almost precise characterization of graph classes with sublinear separators in terms of subexponential expansion.

References

Primary source

Zdenek Dvorak, “Sublinear separators, fragility and subexponential expansion”, arXiv:1404.7219 (2015).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.