Neighbourhood complexity and identification problems for graphs of bounded treewidth and pathwidth

Gaétan Berthe, Florent Foucaud, Tuomo Lehtilä +1

The neighbourhood complexity $nc(G,k)$ of a graph $G$ is a quantity measuring, for a graph $G$ and an integer $k$, the maximum possible number (over all vertex subsets $S$ of size…