Subgraph-closed classes with strongly sublinear separators have subexponential expansion

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 logf(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.

Sources & referencesView supporting material

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.