Charles Explorer logo
🇬🇧

Induced subdivisions and bounded expansion

Publication at Faculty of Mathematics and Physics |
2018

Abstract

We prove that for every graph H and for every integer s, the class of graphs that do not contain K-s, K-s,K-s, or any subdivision of H as induced subgraphs has bounded expansion; this strengthens a result of Kuhn and Osthus (2004). The argument also gives another characterization of graph classes with bounded expansion and of nowhere-dense graph classes.