On weakly distinguishing graph polynomials

MaRDI QIDQ5377223zbMATH OpenFDO

Authors Vsevolod Rakita, Johann A. Makowsky

Publication date 23 May 2019

Full work available at URL https://arxiv.org/abs/1810.13300, https://dmtcs.episciences.org/5340/pdf

zbMATH Keywords

graph polynomials

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph polynomials (05C31)

Abstract: 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.

Recommendations

• Weakly distinguishing graph polynomials on addable properties
• Polychromatic polynomials
• A unified approach to the first derivatives of graph polynomials
• Graphs determined by polynomial invariants
• Clique polynomials and independent set polynomials of graphs

Cited in

(7)

• Weakly distinguishing graph polynomials on addable properties
• Acyclic polynomials of graphs
• Independence equivalence classes of paths and cycles
• On P-unique hypergraphs
• Meta-theorems for graph polynomials
• Beta invariant and chromatic uniqueness of wheels
• My writing

This page was built for publication: On weakly distinguishing graph polynomials

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5377223)