Characterising Bounded Expansion by Neighbourhood Complexity

Felix Reidl, Fernando Sánchez Villaamil, Konstantinos Stavropoulos

We show that a graph class $\mathcal{G}$ has bounded expansion if and only if it has bounded $r$-neighbourhood complexity, i.e. for any vertex set $X$ of any subgraph $H$ of $G\in\cal G…