On the colored Tutte polynomial of a graph of bounded treewidth

We observe that a formula given by Negami [Polynomial invariants of graphs, Trans. Amer. Math. Soc. 299 (1987) 601-622] for the Tutte polynomial of a k-sum of two graphs generalizes to a colored Tutte polynomial. Consequently, an algorithm of Andrzejak [An algorithm for the Tutte polynomials of graphs of bounded treewidth, Discrete Math. 190 (1998) 39-54] may be directly adapted to compute the colored Tutte polynomial of a graph of bounded treewidth in polynomial time. This result has also been proven by Makowsky [Colored Tutte polynomials and Kauffman brackets for graphs of bounded tree width, Discrete Appl. Math. 145 (2005) 276-290], using a different algorithm based on logical techniques.

Title	On the colored Tutte polynomial of a graph of bounded treewidth
Creator	Traldi, Lorenzo
Publisher	Discrete Applied Mathematics
Academic Department	Mathematics
Division	Natural Sciences
Organization	Lafayette College
Date Issued	April 15, 2006
Date Available	2015-04-20T16:48:32Z
Type	Article
Language	English
Keyword	treewidth
	k-sum
	colored Tutte polynomial
	splitting formula
Bibliographic Citation	Traldi, L. (2006 Apr 15) "On the colored Tutte polynomial of a graph of bounded treewidth." Discrete Applied Mathematics 154 (6): 1032-6.
Standard Identifier	Handle 10385/1817
Standard Identifier	DOI 10.1016/j.dam.2005.09.013
Permalink	http://hdl.handle.net/10385/1817
Rights Statement	In Copyright
Rights Holders	Elsevier B.V.