Johann A. Makowsky ; Vsevolod Rakita
-
On Weakly Distinguishing Graph Polynomials
dmtcs:4949 -
Discrete Mathematics & Theoretical Computer Science,
April 2, 2019,
vol. 21 no. 1, ICGT 2018
-
https://doi.org/10.23638/DMTCS-21-1-4On Weakly Distinguishing Graph PolynomialsArticle
Authors: Johann A. Makowsky ; Vsevolod Rakita
NULL##NULL
Johann A. Makowsky;Vsevolod Rakita
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.
Volume: vol. 21 no. 1, ICGT 2018
Published on: April 2, 2019
Accepted on: March 25, 2019
Submitted on: November 1, 2018
Keywords: Mathematics - Combinatorics