Article ID Journal Published Year Pages File Type
4653348 European Journal of Combinatorics 2016 17 Pages PDF
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
,