2008/01/10 by Christian Hoffmann, Hoffmann, Christian
Computer Science · Mathematics · #Combinatorics (math.CO) #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #cs.CC #math.CO
paper · pdf · doi:10.48550/arxiv.0801.1600
5 pages
arxiv created 2008/01/10 · arxiv updated 2009/12/01
We 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.