A Most General Edge Elimination Polynomial - Thickening of Edges

Simple item page
dc.creatorHoffmann, Christian
dc.date2008-01-10
dc.date.accessioned2026-07-07T08:53:40Z
dc.date.available2026-07-07T08:53:40Z
dc.descriptionWe consider a graph polynomial ξ(G;x,y,z) introduced by Averbouch, Godlin, and Makowsky (2007). This graph polynomial simultaneously generalizes the Tutte polynomial as well as a bivariate chromatic polynomial defined by Dohmen, Poenitz and Tittmann (2003). We derive an identity which relates the graph polynomial of a thicked graph (i.e. a graph with each edge replaced by k copies of it) to the graph polynomial 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.
dc.description5 pages
dc.identifierhttps://arxiv.org/abs/0801.1600
dc.identifierhttp://arxiv.org/abs/0801.1600
dc.identifier.urihttp://salesiana.dossiersoluciones.com/handle/123456789/145702
dc.subjectCombinatorics
dc.subjectComputational Complexity
dc.titleA Most General Edge Elimination Polynomial - Thickening of Edges
dc.typetext

Files

Collections

arXiv