2026/07/18 by Gaétan Berthe, Florent Foucaud, Tuomo Lehtilä +1 · 1 voice
#cs.DM #math.CO
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 k) |\N[v]∩ S, v∈ V(G)\| of S-neighbourhoods in G. This notion is important in structural graph theory and algorithm design (especially in parameterized complexity, in particular model checking and kernelization). While generally nc(G,k)≤ 2k and this bound can be achieved, it is known that sparse graphs and structured dense graphs have linear neighbourhood complexity, that is, nc(G,k)∈ O(k) for any such graph G. However, for many graph classes, the best possible constants are not known. We focus on graphs of bounded treewidth and pathwidth, showing that (when k≥ w+1) (i) if G has treewidth w≥ 2, then nc(G,k)≤ (k-w+1)2w+w, and (ii) if G has pathwidth w≥ 2, then nc(G,k)≤ (k-w+2)2w-1+2k-w-2. Moreover, we provide constructions that reach these bounds, whenever w≥ 2 and k≥ 2w+1 (k≥ 2w-1 for pathwidth). Interestingly, in contrast, we also have the tight bound nc(G,k)≤ (7)/(3)k, for graphs G with pathwidth 1 or treewidth 1.