Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
8903627 | European Journal of Combinatorics | 2018 | 6 Pages |
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
ZdenÄk DvoÅák,