Characterising bounded expansion by neighbourhood complexity

Abstract We show that a graph class 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 any G ∈ G , the number of subsets of X which are exact r -neighbourhoods of vertices of H on X is linear in the size of X . This is established by bounding the r -neighbourhood complexity of a graph in terms of both its r - centred colouring number and its weak r -colouring number , which provide known characterisations to the property of bounded expansion.