Article ID Journal Published Year Pages File Type
8903621 European Journal of Combinatorics 2018 5 Pages PDF
Abstract
Let C be a class of graphs that is closed under taking subgraphs. We prove that if for some fixed 0<δ≤1, every n-vertex graph of C has a balanced separator of order O(n1−δ), then any depth-r minor (i.e. minor obtained by contracting disjoint subgraphs of radius at most r) of a graph in C has average degree O((rpolylogr)1∕δ). This confirms a conjecture of Dvořák and Norin.
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, ,