Portal de Periódicos da CAPES

Characterising bounded expansion by neighbourhood complexity

2018; Elsevier BV; Volume: 75; Linguagem: Inglês

10.1016/j.ejc.2018.08.001

1095-9971

Felix Reidl, Fernando Sánchez Villaamil, Konstantinos Stavropoulos,

graph theory and CDMA systems

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 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.