A Most General Edge Elimination Polynomial – Thickening of Edges
Title:
A Most General Edge Elimination Polynomial – Thickening of Edges
Author:
Hoffmann, Christian
Appeared in:
Fundamenta informaticae
Paging:
Volume 98 (2010) nr. 4 pages 373-378
Year:
2010-03-15
Contents:
We consider a graph polynomial ξ (G; x, y, z) introduced by Ilia Averbouch,BennyGodlin, and Johann A.Makowsky (2008). This graph polynomial simultaneously generalizes the Tutte polynomial as well as a bivariate chromatic polynomial defined by Klaus Dohmen, André Pönitz, and Peter Tittmann (2003). We derive an identity which relates the graph polynomial ξ of a thickened graph (i.e. a graph with each edge replaced by k copies of it) to ξ 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 ξ is #P-hard. Thus, ξ supports Johann A. Makowsky's difficult point conjecture for graph polynomials (2008).
Journal description