Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4653348 | European Journal of Combinatorics | 2016 | 17 Pages |
Abstract
Let GG be a subgraph-closed graph class with bounded maximum degree. We show that if GG has balanced separators whose size is smaller than linear by a polynomial factor, then GG has subexponential expansion. This gives a partial converse to a result of Nešetřil and Ossona de Mendez. As an intermediate step, the proof uses a new kind of graph decompositions.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Zdeněk Dvořák,