The Neighborhood Polynomial of Chordal Graphs

We study the neighborhood polynomial and the complexity of its computationfor chordal graphs. The neighborhood polynomial of a graph is the generatingfunction of subsets of its vertices that have a common neighbor. We introduce aparameter for chordal graphs called anchor width and an algorithm to computethe neighborhood polynomial which runs in polynomial time if the anchor widthis polynomially bounded. The anchor width is the maximal number of differentsub-cliques of a clique which appear as a common neighborhood. Furthermore westudy the anchor width for chordal graphs and some subclasses such as chordalcomparability graphs and chordal graphs with bounded leafage. the leafage of achordal graphs is the minimum number of leaves in the host tree of a subtreerepresentation. We show that the anchor width of a chordal graph is at most$n^{\ell}$ where $\ell$ denotes the leafage. This shows that for somesubclasses computing the neighborhood polynomial is possible in polynomial timewhile it is NP-hard for general chordal graphs