Abstract
We observe that a formula given by S. Negami [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 A. Andrzejak [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 J. A. Makowsky [Discrete Appl. Math. 145 (2005), 276-290], using a di¤erent algorithm based on logical techniques.
Introduction
The Tutte polynomial (or dichromate) is one of the most-studied invariants of graphs and matroids; it has many important applications, including vertex colorings, ‡ows, reliability, polynomial invariants of knots, and partition functions of models of statistical mechanics. We refer the reader to [5, 21, 23] for detailed expositions. Many of these applications involve some kind of edge-weighting or edge-coloring; for instance in knot theory an edge of a plane graph represents a crossing of a knot diagram, and is colored to indicate which of the two possible crossings is present.
In our discussion we follow standard terminology of graph theory and matroid theory, as for instance in [5, 17, 22] . A graph G has an associated cycle matroid M , whose rank function is de…ned as follows. For a subset S E = E(G) let G : S be the subgraph of G with V (G : S) = V (G) and E(G : S) = S; if c(G : S) is the number of connected components of G : S then r(S) = jV (G)j c(G : S). Whenever we discuss matroids, we presume that graphs are included in the discussion via their cycle matroids. for any other element e. The empty matroid ; has T (;) = 1. Another de…nition utilizes a subset expansion:
Here r denotes the rank function of the matroid M . A third de…nition of the Tutte polynomial is phrased in terms of basis activities; this de…nition will not be useful in this note, so we do not discuss it in detail.
The evident exponential character of these de…nitions suggests the result of [10] that computing T (M )
is #P -hard in general.
Pathwidth and treewidth were introduced in [18, 19, 20] as measures of the structural complexity of graphs, and since then these notions have proven to be of great interest. Many algorithmically intractable problems become tractable when restricted to graphs of bounded treewidth; in particular, the result that computing
is tractable for graphs of bounded treewidth was mentioned by Welsh in [21] , and proven by Andrzejak in [2] . (See also [15] .) The crucial ingredients of Andrzejak's proof are algorithms of Bodlaender and Hagerup which …nd a binary tree decomposition of a graph G of treewidth bounded by k [3, 4] and Negami's splitting formula for the Tutte polynomial of the k-sum of two graphs [14] ; the splitting formula is used repeatedly as G is constructed from simpler graphs according to a binary tree decomposition. Makowsky has recently proven a broad generalization of this result [11, 12, 13] , using logical techniques; this generalization covers colored versions of the Tutte polynomial and many other kinds of generating functions de…nable in monadic second order logic.
In this note we observe that Negami's splitting formula can be extended to a colored version of the Tutte polynomial, and hence that for this polynomial and its evaluations (like the Kau¤man bracket) a colored version of Andrzejak's algorithm may be used. As Makowsky observes in [13] , the greater generality of logical techniques comes at a signi…cant computational price; an algorithm based on Negami's splitting formula is less general but more practical.
Negami' s splitting formula, with colors
Suppose a matroid M on a set E is colored by a function c : E ! , and suppose that for each 2 elements x ; y of a …eld have been chosen. (We trust that there will be no confusion between the color c(e)
of an edge of G and the number of components c(H) of a subgraph of G.) Zaslavsky [24] calls
the normal function of the colored matroid. R(M; c) is probably the most natural colored version of T (M ), though there are many others; see [6, 9, 24] and the references mentioned there. R(M; c) has a basis activities expansion analogous to that of T (M ), and it satis…es a colored deletion-contraction recursion: Theorem 2.1. Let G be a k-sum of subgraphs H and K, i.e.,
. Then there is a formula which depends only on k, jV (G)j Let G be a graph, and suppose E = E(G) is colored by c : E ! . Suppose that t is an element of a …eld and for each 2 , x and y are also elements of the …eld; for instance the …eld in question could be the …eld of quotients of the polynomial ring Z[ftg [ fx ; y : 2 g]. Then the deletion-contraction formula f (G; c) = x c(e) f (G=e; c) + y c(e) f (G e; c), together with the initial condition that if E(G) = ; then f (G; c) = t jV (G)j , yields a well-de…ned invariant f (G; c).
Proof. This is true by de…nition if E(G) = ;. Suppose inductively that e 0 2 E(G); then
It follows from Proposition 2.2 that f (G; c) is closely related to R(M; c); the corresponding relationship between the uncolored invariants f (G) and T (M ) is well known [14, 16] .
each x c(e) 7 ! x c(e) (Y 1) and each y c(e) 7 ! y c(e) . Also, t c(G) f (G; c) is obtained from R(M; c) by evaluating
and each y c(e) 7 ! y c(e) .
Suppose G is a k-sum of subgraphs H and K, i.e.,
, and let (U ) be the set of all partitions of U ; (U ) is a lattice when ordered by re…nement. For ; 0 2 (U ) let ^ 0 be the meet in this lattice.
That is, ^ 0 is the partition de…ned by: u and u 0 are in the same element of ^ 0 if there is a sequence u = u 1 ; u 2 ; af76:e4bb:d472:9fe5:10c0:37a3:766a:5b99:; u a = u 0 such that when 1 i < a, u i and u i+1 are in the same element of either or 0 . Using an arbitrary ordering of (U ) as f 1 ; 2 ; af76:e4bb:d472:9fe5:10c0:37a3:766a:5b99:g Negami [14] de…nes T k to be the square matrix whose (i; j) entry is t j i^ j j and observes that if t is an indeterminate then T k is nonsingular: the product of terms on 4 the diagonal is clearly of higher degree than any other product of terms that contributes to the determinant, so the determinant must be nonzero.
For 2 (U ) a contraction G= may be de…ned in the obvious way: each element of gives rise to a single vertex of G= and each edge e of G gives rise to an edge e of G= which connects the vertices of G= containing the end-vertices of e. Clearly non-loop edges of G may become loops in G= , and isthmuses of G may become non-isthmuses in G= . Andrzejak [2] gives a detailed discussion of an algorithm which calculates T (M ) by determining a binary, rooted tree decomposition of G and repeatedly using Negami's splitting formula; the algorithm runs in time O(n 2+7 log 2 c ), where n = jV (G)j and c is twice the number of partitions of a set with 3k + 3 elements, presuming that arithmetic operations are performed at constant cost. The same discussion applies here, with the caveat that the cost of arithmetic operations may depend on the …eld that contains the x and y .
Similarly, if we consider the relationship between R(M; c) and the rank function of M we conclude Corollary 2.6. For a graph G of bounded treewidth the rank function of the cycle matroid M may be determined in polynomial time.
We do not know how these results may generalize to matroids which are not cycle matroids of graphs;
Negami's argument requires both the simple deletion-contraction recursion of f and the presence of vertices in H \ K, so it does not apply to arbitrary matroids. There are results in the literature regarding Tutte polynomials of generalized parallel connections of general matroids [1, 7] , but those generalized parallel connections are not su¢ ciently general to include all k-sums of graphs.
Acknowledgments


{'paper_id': '18910', 'title': 'On the colored Tutte polynomial of a graph of bounded treewidth', 's2_url': 'https://api.semanticscholar.org/CorpusID:18910', 'source': 'S2ORC'}