A Most General Edge Elimination Polynomial – Thickening of Edges

Issue title: Bridging Logic and Computer Science: to Johann A. Makowsky for his 60th birthday

Article type: Research Article

Authors: Hoffmann, Christian

Affiliations: Universität des Saarlandes, Informatik, Postfach 151150, 66041 Saarbrücken, Germany. E-mail: hoffmann@cs.uni-sb.de

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

DOI: 10.3233/FI-2010-233

Journal: Fundamenta Informaticae, vol. 98, no. 4, pp. 373-378, 2010