A Most General Edge Elimination Polynomial - Thickening of Edges

作者：Hoffmann Christian^*

来源：Fundamenta Informaticae, 2010, 98(4): 373-378.

DOI：10.3233/FI-2010-233

We consider a graph polynomial xi(G; x, y, z) introduced by Ilia Averbouch, Benny Godlin, and Johann A. Makowsky (2008). This graph polynomial simultaneously generalizes the Tutte polynomial as well as a bivariate chromatic polynomial defined by Klaus Dohmen, Andre Ponitz, and Peter Tittmann (2003). We derive an identity which relates the graph polynomial xi of a thickened graph (i.e. a graph with each edge replaced by k copies of it) to xi of the original graph. As a consequence, we observe that at every point (x, y, z), except for points lying within some set of dimension 2, evaluating xi is #P-hard. Thus, xi supports Johann A. Makowsky's difficult point conjecture for graph polynomials (2008).

• 出版日期2010