Subgraph-closed classes with strongly sublinear separators have subexponential expansion
Subgraph-closed classes with strongly sublinear separators have subexponential expansion
Let be a subgraph-closed class of graphs. Suppose that has strongly sublinear separators. Subexponential expansion conjecture. The expansion of is subexponential; that is, there exists a function with such that the expansion of is bounded by . 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.