A Most General Edge Elimination Polynomial – Thickening of Edges
2010; IOS Press; Volume: 98; Issue: 4 Linguagem: Inglês
10.3233/fi-2010-233
ISSN1875-8681
Autores Tópico(s)Graph theory and applications
ResumoWe 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, Andre Ponitz, 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).
Referência(s)