Article ID Journal Published Year Pages File Type
8903627 European Journal of Combinatorics 2018 6 Pages PDF
Abstract
We prove that for every graph H and for every integer s, the class of graphs that do not contain Ks, Ks,s, or any subdivision of H as induced subgraphs has bounded expansion; this strengthens a result of Kühn and Osthus (2004). The argument also gives another characterization of graph classes with bounded expansion and of nowhere-dense graph classes.
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
,