On Weakly Distinguishing Graph Polynomials
Johann A. Makowsky, Vsevolod Rakita · Discrete Mathematics & Theoretical Computer Science · 2019
A univariate graph polynomial P(G;X) is weakly distinguishing if for almost all finite graphs G there is a finite graph H with P(G;X)=P(H;X). We show that the clique polynomial and the independence polynomial are weakly distinguishing. Furthermore, we show that generating functions of induced subgraphs with property C are weakly distinguishing provided that C is of bounded degeneracy or tree-width. The same holds for the harmonious chromatic polynomial.