4 problems

A graph class has almost linear neighborhood complexity if, for every graph $G$ in the class and every subset $X\subseteq V(G)$, the number of distinct neighborhoods within $X$ of…

Linear neighborhood-complexity conjecture. Every hereditary small class of graphs has neighborhood complexity $O(n)$.

Let $G$ be a planar graph, let $A$ be a nonempty subset of its vertices, and let $r$ be a nonnegative integer. The neighborhood complexity of $G$ with respect to $A$ and radius $r$…

The neighborhood-complexity characterization. The class $\mathcal{C}$ is nowhere dense if and only if there exists a function $f_{\mathrm{nei}}(r,\varepsilon)$ such that