Charles Explorer logo
🇨🇿

Induced subdivisions and bounded expansion

Publikace na Matematicko-fyzikální fakulta |
2018

Tento text není v aktuálním jazyce dostupný. Zobrazuje se verze "en".Abstrakt

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.