Tutte polynomial

Definition. For an undirected graph $G=(V,E)$ one may define the Tutte polynomial as

:$T\_G(x,y)=\backslash sum\backslash nolimits\_\{A\backslash subseteq\; E\}\; (x-1)^\{k(A)-k(E)\}(y-1)^\{k(A)+|A|-|V|\},$

where $k(A)$ denotes the number of connected components of the graph $(V,A)$.

In this definition it is clear that $T\_G$ is well-defined and a polynomial in $x$ and $y$.

The same definition can be given using slightly different notation by letting $r(A)=|V|-k(A)$ denote the rank of the graph $(V,A)$. Then the Whitney rank generating function is defined as

:$R\_G(u,v)=\backslash sum\backslash nolimits\_\{A\backslash subseteq\; E\}\; u^\{r(E)-r(A)\}\; v^$

is equivalent to $T\_G$ under the transformation{{harvnb|Sokal|2005|loc=eq. (2.26)}}.

:$T\_G(x,\; y)=(x-1)^\{-k(E)\}(y-1)^\{-|V|\}\; \backslash cdot\; Z\_G\backslash Big((x-1)(y-1),\backslash ;\; y-1\backslash Big).$

The Tutte polynomial factors into connected components. If $G$ is the union of disjoint graphs $H$ and $H\text{'}$ then

: $T\_G=\; T\_H\; \backslash cdot\; T\_\{H\text{'}\}$

If $G$ is planar and $G^*$ denotes its dual graph then

: $T\_G(x,y)=\; T\_\{G^*\}\; (y,x)$

Especially, the chromatic polynomial of a planar graph is the flow polynomial of its dual. Tutte refers to such functions as V-functions.

Isomorphic graphs have the same Tutte polynomial, but the converse is not true. For example, the Tutte polynomial of every tree on $m$ edges is $x^m$.

Tutte polynomials are often given in tabular form by listing the coefficients $t\_\{ij\}$ of $x^iy^j$ in row $i$ and column $j$. For example, the Tutte polynomial of the Petersen graph,

:$\backslash begin\{align\}$

36 x &+ 120 x^2 + 180 x^3 + 170x^4+114x^5 + 56x^6 +21 x^7 + 6x^8 + x^9 \\

&+ 36y +84 y^2 + 75 y^3 +35 y^4 + 9y^5+y^6 \\

&+ 168xy + 240x^2y +170x^3y +70 x^4y + 12x^5 y \\

&+ 171xy^2+105 x^2y^2 + 30x^3y^2 \\

&+ 65xy^3 +15x^2y^3 \\

&+10xy^4,

\end{align}

is given by the following table.

Other example, the Tutte polynomial of the octahedron graph is given by

:$\backslash begin\{align\}$

&12\,{y}^{2}{x}^{2}+11\,x+11\,y+40\,{y}^{3}+32\,{

y}^{2}+46\,yx+24\,x{y}^{3}+52\,x{y}^{2} \\

&+25\,{x}^{2}+29\,{y}^{4}+15\,{y

}^{5}+5\,{y}^{6}+6\,{y}^{4}x \\

&+39\,y{x}^{2}+20\,{x}^{3}+{y}^{7}+8\,y{x}^

{3}+7\,{x}^{4}+{x}^{5}

\end{align}

W. T. Tutte’s interest in the deletion–contraction formula started in his undergraduate days at Trinity College, Cambridge, originally motivated by perfect rectangles and spanning trees. He often applied the formula in his research and “wondered if there were other interesting functions of graphs, invariant under isomorphism, with similar recursion formulae.”{{harvnb|Tutte|2004}}. R. M. Foster had already observed that the chromatic polynomial is one such function, and Tutte began to discover more. His original terminology for graph invariants that satisfy the deletion–contraction recursion was W-function, and V-function if multiplicative over components. Tutte writes, “Playing with my W-functions I obtained a two-variable polynomial from which either the chromatic polynomial or the flow-polynomial could be obtained by setting one of the variables equal to zero, and adjusting signs.” Tutte called this function the dichromate, as he saw it as a generalization of the chromatic polynomial to two variables, but it is usually referred to as the Tutte polynomial. In Tutte’s words, “This may be unfair to Hassler Whitney who knew and used analogous coefficients without bothering to affix them to two variables.” (There is “notable confusion”Welsh. about the terms dichromate and dichromatic polynomial, introduced by Tutte in different paper, and which differ only slightly.) The generalisation of the Tutte polynomial to matroids was first published by Crapo, though it appears already in Tutte’s thesis.{{harvnb|Farr|2007}}.

Independently of the work in algebraic graph theory, Potts began studying the partition function of certain models in statistical mechanics in 1952. The work by Fortuin and Kasteleyn{{harvnb|Fortuin|Kasteleyn|1972}}. on the random cluster model, a generalisation of the Potts model, provided a unifying expression that showed the relation to the Tutte polynomial.

At various points and lines of the $(x,y)$-plane, the Tutte polynomial evaluates to quantities that have been studied in their own right in diverse fields of mathematics and physics. Part of the appeal of the Tutte polynomial comes from the unifying framework it provides for analysing these quantities.

{{Main|Chromatic polynomial}}

Image:Chromatic in the Tutte plane.jpg

At $y=0$, the Tutte polynomial specialises to the chromatic polynomial,{{Dubious|Specialization to polynomials|date=December 2024}}

:$\backslash chi\_G(\backslash lambda)\; =\; (-1)^$

gives the number of acyclic orientations.

{{Main|Jones polynomial}}

Image:Jones in the Tutte plane.jpg

Along the hyperbola $xy=1$, the Tutte polynomial of a planar graph specialises to the Jones polynomial of an associated alternating knot.{{Dubious|Specialization to polynomials|date=December 2024}}

$T\_G(2,1)$ counts the number of forests, i.e., the number of acyclic edge subsets.

$T\_G(1,1)$ counts the number of spanning forests (edge subsets without cycles and the same number of connected components as G). If the graph is connected, $T\_G(1,1)$ counts the number of spanning trees.

$T\_G(1,2)$ counts the number of spanning subgraphs (edge subsets with the same number of connected components as G).

$T\_G(2,0)$ counts the number of acyclic orientations of G.{{harvnb|Welsh|1999}}.

$T\_G(0,2)$ counts the number of strongly connected orientations of G.{{harvnb|Las Vergnas|1980}}.

$T\_G(2,2)$ is the number $2^$

If G is a 4-regular graph, then

:$(-1)^\{|V|+k(G)\}T\_G(0,-2)$

counts the number of Eulerian orientations of G. Here $k(G)$ is the number of connected components of G.

If G is the m × n grid graph, then $2\; T\_G(3,3)$ counts the number of ways to tile a rectangle of width 4m and height 4n with T-tetrominoes.{{harvnb|Korn|Pak|2004}}.See {{harvnb|Korn|Pak|2003}} for combinatorial interpretations of many other points.

If G is a planar graph, then $2\; T\_G(3,3)$ equals the sum over weighted Eulerian orientations in a medial graph of G, where the weight of an orientation is 2 to the number of saddle vertices of the orientation (that is, the number of vertices with incident edges cyclicly ordered "in, out, in out").{{harvnb|Las Vergnas|1988}}.

{{Main|Ising model|Potts model}}

Image:Potts and Ising in the Tutte plane.jpg

Define the hyperbola in the xy−plane:

:$H\_2:\; \backslash quad\; (x-1)(y-1)=2,$

the Tutte polynomial specialises to the partition function, $Z(\backslash cdot),$ of the Ising model studied in statistical physics.{{Dubious|Specialization to polynomials|date=December 2024}} Specifically, along the hyperbola $H\_2$ the two are related by the equation:{{harvnb|Welsh|1993|p=62}}.

:$Z(G)\; =\; 2\backslash left(e^\{-\backslash alpha\}\backslash right)^$

{{Main|Nowhere-zero flow}}

Image:Flow in the Tutte plane.jpg

At $x=0$, the Tutte polynomial specialises to the flow polynomial studied in combinatorics.{{Dubious|Specialization to polynomials|date=December 2024}} For a connected and undirected graph G and integer k, a nowhere-zero k-flow is an assignment of “flow” values $1,2,\backslash dots,k-1$ to the edges of an arbitrary orientation of G such that the total flow entering and leaving each vertex is congruent modulo k. The flow polynomial $C\_G(k)$ denotes the number of nowhere-zero k-flows. This value is intimately connected with the chromatic polynomial, in fact, if G is a planar graph, the chromatic polynomial of G is equivalent to the flow polynomial of its dual graph $G^*$ in the sense that

Theorem (Tutte).

:$C\_G(k)=k^\{-1\}\; \backslash chi\_\{G^*\}(k).$

The connection to the Tutte polynomial is given by:

: $C\_G(k)=\; (-1)^\{|E|-|V|+k(G)\}\; T\_G(0,1-k).$

{{Main|Connectivity (graph theory)}}

Image:Reliability in the Tutte plane.jpg

At $x=1$, the Tutte polynomial specialises to the all-terminal reliability polynomial studied in network theory.{{Dubious|Specialization to polynomials|date=December 2024}} For a connected graph G remove every edge with probability p; this models a network subject to random edge failures. Then the reliability polynomial is a function $R\_G(p)$, a polynomial in p, that gives the probability that every pair of vertices in G remains connected after the edges fail. The connection to the Tutte polynomial is given by

:$R\_G(p)\; =\; (1-p)^\{|V|-k(G)\}\; p^\{|E|-|V|+k(G)\}\; T\_G\; \backslash left\; (1,\; \backslash tfrac\{1\}\{p\}\; \backslash right).$

Tutte also defined a closer 2-variable generalization of the chromatic polynomial, the dichromatic polynomial of a graph. This is

:$Q\_G(u,v)\; =\; \backslash sum\backslash nolimits\_\{A\; \backslash subseteq\; E\}\; u^\{k(A)\}\; v^\{|A|-|V|+k(A)\},$

where $k(A)$ is the number of connected components of the spanning subgraph (V,A). This is related to the corank-nullity polynomial by

:$Q\_G(u,v)\; =\; u^\{k(G)\}\; \backslash ,\; R\_G(u,v).$

The dichromatic polynomial does not generalize to matroids because k(A) is not a matroid property: different graphs with the same matroid can have different numbers of connected components.

The Martin polynomial $m\_\{\backslash vec\{G\}\}(x)$ of an oriented 4-regular graph $\backslash vec\{G\}$ was defined by Pierre Martin in 1977.{{harvnb|Martin|1977}}. He showed that if G is a plane graph and $\backslash vec\{G\}\_m$ is its directed medial graph, then

:$T\_G(x,x)\; =\; m\_\{\backslash vec\{G\}\_m\}(x).$

{{Main|Deletion–contraction formula}}

Image:deletion-contraction.svg. Red edges are deleted in the left child and contracted in the right child. The resulting polynomial is the sum of the monomials at the leaves, $x^3+2x^2\; +y^2+2xy+x+y$. Based on {{harvtxt|Welsh|Merino|2000}}.]]

The deletion–contraction recurrence for the Tutte polynomial,

: $T\_G(x,y)=\; T\_\{G\; \backslash setminus\; e\}(x,y)\; +\; T\_\{G/e\}(x,y),\; \backslash qquad\; e\; \backslash text\{\; not\; a\; loop\; nor\; a\; bridge.\}$

immediately yields a recursive algorithm for computing it for a given graph: as long as you can find an edge e that is not a loop or bridge, recursively compute the Tutte polynomial for when that edge is deleted, and when that edge is contracted. Then add the two sub-results together to get the overall Tutte polynomial for the graph.

The base case is a monomial $x^my^n$ where m is the number of bridges, and n is the number of loops.

Within a polynomial factor, the running time t of this algorithm can be expressed in terms of the number of vertices n and the number of edges m of the graph,

:$t(n+m)=\; t(n+m-1)\; +\; t(n+m-2),$

a recurrence relation that scales as the Fibonacci numbers with solution{{harvnb|Wilf|1986|p=46}}.

:$t(n+m)=\; \backslash left\; (\backslash frac\{1+\backslash sqrt\{5\}\}\{2\}\; \backslash right\; )^\{n+m\}\; =\; O\; \backslash left\; (1.6180^\{n+m\}\; \backslash right\; ).$

The analysis can be improved to within a polynomial factor of the number $\backslash tau(G)$ of spanning trees of the input graph.{{harvnb|Sekine|Imai|Tani|1995}}. For sparse graphs with $m=O(n)$ this running time is $\backslash exp(O(n))$. For regular graphs of degree k, the number of spanning trees can be bounded by

:$\backslash tau(G)\; =\; O\; \backslash left\; (\backslash nu\_k^n\; n^\{-1\}\; \backslash log\; n\; \backslash right\; ),$

where

:$\backslash nu\_k\; =\; \backslash frac\{(k-1)^\{k-1\}\}\{(k^2-2k)^\{\backslash frac\{k\}\{2\}-1\}\}.$

so the deletion–contraction algorithm runs within a polynomial factor of this bound. For example:{{harvnb|Chung|Yau|1999}}, following {{harvnb|Björklund|Husfeldt|Kaski|Koivisto|2008}}.

:$\backslash nu\_5\; \backslash approx\; 4.4066.$

In practice, graph isomorphism testing is used to avoid some recursive calls. This approach works well for graphs that are quite sparse and exhibit many symmetries; the performance of the algorithm depends on the heuristic used to pick the edge e.{{harvnb|Haggard|Pearce|Royle|2010}}.{{harvnb|Pearce|Haggard|Royle|2010}}.

In some restricted instances, the Tutte polynomial can be computed in polynomial time, ultimately because Gaussian elimination efficiently computes the matrix operations determinant and Pfaffian. These algorithms are themselves important results from algebraic graph theory and statistical mechanics.

$T\_G(1,1)$ equals the number $\backslash tau(G)$ of spanning trees of a connected graph. This is

computable in polynomial time as the determinant of a maximal principal submatrix of the Laplacian matrix of G, an early result in algebraic graph theory known as Kirchhoff’s Matrix–Tree theorem. Likewise, the dimension of the bicycle space at $T\_G(-1,-1)$ can be computed in polynomial time by Gaussian elimination.

For planar graphs, the partition function of the Ising model, i.e., the Tutte polynomial at the hyperbola $H\_2$, can be expressed as a Pfaffian and computed efficiently via the FKT algorithm. This idea was developed by Fisher, Kasteleyn, and Temperley to compute the number of dimer covers of a planar lattice model.

Using a Markov chain Monte Carlo method, the Tutte polynomial can be arbitrarily well approximated along the positive branch of $H\_2$, equivalently, the partition function of the ferromagnetic Ising model. This exploits the close connection between the Ising model and the problem of counting matchings in a graph. The idea behind this celebrated result of Jerrum and Sinclair{{harvnb|Jerrum|Sinclair|1993}}. is to set up a Markov chain whose states are the matchings of the input graph. The transitions are defined by choosing edges at random and modifying the matching accordingly. The resulting Markov chain is rapidly mixing and leads to “sufficiently random” matchings, which can be used to recover the partition function using random sampling. The resulting algorithm is a fully polynomial-time randomized approximation scheme (fpras).

Several computational problems are associated with the Tutte polynomial. The most straightforward one is

;Input: A graph $G$

;Output: The coefficients of $T\_G$

In particular, the output allows evaluating $T\_G(-2,0)$ which is equivalent to counting the number of 3-colourings of G. This latter question is #P-complete, even when restricted to the family of planar graphs, so the problem of computing the coefficients of the Tutte polynomial for a given graph is #P-hard even for planar graphs.

Much more attention has been given to the family of problems called Tutte$(x,y)$ defined for every complex pair $(x,y)$:

;Input: A graph $G$

;Output: The value of $T\_G(x,y)$

The hardness of these problems varies with the coordinates $(x,y)$.

[[Image:Tractable points of the Tutte polynomial in the real plane.svg|thumb|300px|right|

The Tutte plane.

Every point $(x,y)$ in the real plane corresponds to a computational problem $T\_G(x,y)$.

At any red point, the problem is polynomial-time computable;

at any blue point, the problem is #P-hard in general, but polynomial-time computable for planar graphs; and

at any point in the white regions, the problem is #P-hard even for bipartite planar graphs.

]]

If both x and y are non-negative integers, the problem $T\_G(x,y)$ belongs to #P. For general integer pairs, the Tutte polynomial contains negative terms, which places the problem in the complexity class GapP, the closure of #P under subtraction. To accommodate rational coordinates $(x,y)$, one can define a rational analogue of #P.{{harvnb|Goldberg|Jerrum|2008}}.

The computational complexity of exactly computing $T\_G(x,y)$ falls into one of two classes for any $x,\; y\; \backslash in\; \backslash mathbb\{C\}$. The problem is #P-hard unless $(x,y)$ lies on the hyperbola $H\_1$ or is one of the points

:$\backslash left\; \backslash \{\; (1,1),\; (-1,-1),\; (0,-1),\; (-1,0),\; (i,-i),\; (-i,i),\; \backslash left(j,j^2\; \backslash right),\; \backslash left(j^2,j\; \backslash right)\; \backslash right\; \backslash \},\; \backslash qquad\; j\; =\; e^\{\backslash frac\{2\; \backslash pi\; i\}\{3\}\}.$

in which cases it is computable in polynomial time.{{harvnb|Jaeger|Vertigan|Welsh|1990}}. If the problem is restricted to the class of planar graphs, the points on the hyperbola $H\_2$ become polynomial-time computable as well. All other points remain #P-hard, even for bipartite planar graphs.{{harvnb|Vertigan|Welsh|1992}}. In his paper on the dichotomy for planar graphs, Vertigan claims (in his conclusion) that the same result holds when further restricted to graphs with vertex degree at most three, save for the point $T\_G(0,-2)$, which counts nowhere-zero Z₃-flows and is computable in polynomial time.{{harvnb|Vertigan|2005}}.

These results contain several notable special cases. For example, the problem of computing the partition function of the Ising model is #P-hard in general, even though celebrated algorithms of Onsager and Fisher solve it for planar lattices. Also, the Jones polynomial is #P-hard to compute. Finally, computing the number of four-colorings of a planar graph is #P-complete, even though the decision problem is trivial by the four color theorem. In contrast, it is easy to see that counting the number of three-colorings for planar graphs is #P-complete because the decision problem is known to be NP-complete via a parsimonious reduction.

The question which points admit a good approximation algorithm has been very well studied. Apart from the points that can be computed exactly in polynomial time, the only approximation algorithm known for $T\_G(x,y)$ is Jerrum and Sinclair’s FPRAS, which works for points on the “Ising” hyperbola $H\_2$ for y > 0. If the input graphs are restricted to dense instances, with degree $\backslash Omega(n)$, there is an FPRAS if x ≥ 1, y ≥ 1.For the case x ≥ 1 and y = 1, see {{harvnb|Annan|1994}}. For the case x ≥ 1 and y > 1, see {{harvnb|Alon|Frieze|Welsh|1995}}.

Even though the situation is not as well understood as for exact computation, large areas of the plane are known to be hard to approximate.

• Bollobás–Riordan polynomial
• A Tutte–Grothendieck invariant is any evaluation of the Tutte polynomial

{{Reflist|colwidth=25em}}

{{refbegin|colwidth=25em}}

• {{Citation

| last1 = Alon

| first1 = N.

| last2 = Frieze

| first2 = A.

| last3 = Welsh

| first3 = D. J. A.

| author-link3 = Dominic Welsh

| title = Polynomial time randomized approximation schemes for Tutte-Gröthendieck invariants: The dense case

| journal = Random Structures and Algorithms

| volume = 6

| issue = 4

| pages = 459–478

| year = 1995

| doi = 10.1002/rsa.3240060409

}}.

• {{Citation

| last1 = Annan

| first1 = J. D.

| title = A Randomised Approximation Algorithm for Counting the Number of Forests in Dense Graphs

| journal = Combinatorics, Probability and Computing

| volume = 3

| issue = 3

| pages = 273–283

| year = 1994

| doi = 10.1017/S0963548300001188

}}.

• {{Citation

| last = Biggs

| first = Norman

| title = Algebraic Graph Theory

| edition = 2nd

| publisher = Cambridge University Press

| year = 1993

| isbn = 0-521-45897-8

}}.

• {{Citation

| first1 = Andreas

| last1 = Björklund

| first2 = Thore

| last2 = Husfeldt

| first3 = Petteri

| last3 = Kaski

| first4 = Mikko

| last4 = Koivisto

| contribution = Computing the Tutte polynomial in vertex-exponential time

| title = Proc. of the 47th annual IEEE Symposium on Foundations of Computer Science (FOCS 2008)

| pages = 677–686

| year = 2008

| doi = 10.1109/FOCS.2008.40

| isbn = 978-0-7695-3436-7

| arxiv = 0711.2585

}}.

• {{Citation

| last1 = Bollobás

| first1 = Béla

| author1-link = Béla Bollobás

| title = Modern Graph Theory

| publisher = Springer

| year = 1998

| isbn = 978-0-387-98491-9

}}.

• {{Citation

| last1 = Chung

| first1 = Fan

| author1-link = Fan Chung

| last2 = Yau

| first2 = S.-T.

| author2-link = Shing-Tung Yau

| title = Coverings, heat kernels and spanning trees

| journal = Electronic Journal of Combinatorics

| volume = 6

| page = R12

| year = 1999

| doi = 10.37236/1444

| mr = 1667452

| url = http://www.combinatorics.org/Volume_6/Abstracts/v6i1r12.html

}}.

• {{Citation

| last1 = Crapo

| first1 = Henry H.

| author-link1 = Henry Crapo (mathematician)

| title = The Tutte polynomial

| journal = Aequationes Mathematicae

| volume = 3

| issue = 3

| pages = 211–229

| year = 1969

| doi = 10.1007/bf01817442

}}.

• {{Citation

| last = Farr

| first = Graham E.

| editor1-last = Grimmett

| editor1-first = Geoffrey

| editor1-link = Geoffrey Grimmett

| editor2-last = McDiarmid

| editor2-first = Colin

| contribution = Tutte-Whitney polynomials: some history and generalizations

| title = Combinatorics, complexity, and chance. A tribute to Dominic Welsh

| series = Oxford Lecture Series in Mathematics and its Applications

| volume = 34

| pages = 28–52

| year = 2007

| publisher = Oxford University Press

| isbn = 978-0-19-857127-8

| zbl = 1124.05020

}}.

• {{Citation

| last1 = Fortuin

| first1 = Cees M.

| last2 = Kasteleyn

| first2 = Pieter W.

| title = On the random-cluster model: I. Introduction and relation to other models

| journal = Physica

| volume = 57

| issue = 4

| pages = 536–564

| year = 1972

| publisher = Elsevier

| issn = 0031-8914

| doi = 10.1016/0031-8914(72)90045-6

| bibcode = 1972Phy....57..536F

}}.

• {{Citation

| last1 = Godsil

| first1 = Chris

| author-link1 = Chris Godsil

| last2 = Royle

| first2 = Gordon

| author-link2 = Gordon Royle

| title = Algebraic Graph Theory

| publisher = Springer

| year = 2004

| isbn = 978-0-387-95220-8

}}.

• {{Citation

| last1 = Goldberg

| first1 = Leslie Ann

| author1-link = Leslie Ann Goldberg

| last2 = Jerrum

| first2 = Mark

| author2-link = Mark Jerrum

| title = Inapproximability of the Tutte polynomial

| journal = Information and Computation

| volume = 206

| issue = 7

| pages = 908–929

| year = 2008

| doi = 10.1016/j.ic.2008.04.003

| arxiv = cs/0605140

}}.

• {{Citation

| last1 = Haggard

| first1 = Gary

| last2 = Pearce

| first2 = David J.

| last3 = Royle

| first3 = Gordon

| title = Computing Tutte polynomials

| journal = ACM Transactions on Mathematical Software

| volume = 37

| issue = 3

| page = Art. 24, 17

| year = 2010

| doi = 10.1145/1824801.1824802

| mr = 2738228

}}.

• {{Citation

| last1 = Jaeger

| first1 = F.

| last2 = Vertigan

| first2 = D. L.

| last3 = Welsh

| first3 = D. J. A.

| authorlink3 = Dominic Welsh

| title = On the computational complexity of the Jones and Tutte polynomials

| journal = Mathematical Proceedings of the Cambridge Philosophical Society

| volume = 108

| issue = 1

| pages = 35–53

| year = 1990

| doi = 10.1017/S0305004100068936

| bibcode = 1990MPCPS.108...35J

}}.

• {{Citation

| last1 = Jerrum

| first1 = Mark

| author-link = Mark Jerrum

| last2 = Sinclair

| first2 = Alistair

| author2-link = Alistair Sinclair

| title = Polynomial-time approximation algorithms for the Ising model

| journal = SIAM Journal on Computing

| volume = 22

| issue= 5

| pages = 1087–1116

| year = 1993

| doi= 10.1137/0222066

| url = http://www-static.cc.gatech.edu/~vigoda/Permanent.pdf

}}.

• {{Citation

| last1 = Korn

| first1 = Michael

| last2 = Pak

| first2 = Igor

| author2-link = Igor Pak

| title = Combinatorial evaluations of the Tutte polynomial

| type = preprint

| year = 2003

| url = https://www.math.ucla.edu/~pak/papers/tutte7color.pdf

}}.

• {{Citation

| last1 = Korn

| first1 = Michael

| last2 = Pak

| first2 = Igor

| author2-link = Igor Pak

| title = Tilings of rectangles with T-tetrominoes

| journal = Theoretical Computer Science

| volume = 319

| issue = 1–3

| pages = 3–27

| year = 2004

| doi = 10.1016/j.tcs.2004.02.023

| doi-access = free

}}.

• {{Citation

| last = Las Vergnas

| first = Michel

| authorlink = Michel Las Vergnas

| title = Convexity in oriented matroids

| journal = Journal of Combinatorial Theory

| series = Series B

| volume = 29

| issue = 2

| pages = 231–243

| year = 1980

| issn = 0095-8956

| doi = 10.1016/0095-8956(80)90082-9

| mr = 586435

| doi-access = free

}}.

• {{Citation

| last1 = Las Vergnas

| first1 = Michel

| author1-link = Michel Las Vergnas

| title = On the evaluation at (3, 3) of the Tutte polynomial of a graph

| journal = Journal of Combinatorial Theory

| series = Series B

| volume = 45

| issue = 3

| pages = 367–372

| year = 1988

| issn = 0095-8956

| doi = 10.1016/0095-8956(88)90079-2

| doi-access = free

}}.

• {{Citation

| last = Martin

| first = Pierre

| title = Enumérations Eulériennes dans les multigraphes et invariants de Tutte-Grothendieck

| trans-title = Eulerian Enumerations in multigraphs and Tutte-Grothendieck invariants

| type = Ph.D. thesis

| publisher = Joseph Fourier University

| year = 1977

| language = French

| url = http://tel.archives-ouvertes.fr/tel-00287330/en

}}.

• {{Citation

| last1 = Pearce

| first1 = David J.

| last2 = Haggard

| first2 = Gary

| last3 = Royle

| first3 = Gordon

| title = Edge-selection heuristics for computing Tutte polynomials

| journal = Chicago Journal of Theoretical Computer Science

| page = Article 6, 14

| year = 2010

| url = http://cjtcs.cs.uchicago.edu/articles/2010/6/cats9-3-1.pdf

| mr = 2659710

}}.

• {{Citation

| last1 = Sekine

| first1 = Kyoko

| last2 = Imai

| first2 = Hiroshi

| last3 = Tani

| first3 = Seiichiro

| contribution = Computing the Tutte polynomial of a graph of moderate size

| title = Algorithms and computations (Cairns, 1995)

| volume = 1004

| pages = 224–233

| series = Lecture Notes in Computer Science

| publisher = Springer

| year = 1995

| doi = 10.1007/BFb0015427

| isbn = 978-3-540-60573-7

| mr = 1400247

}}.

• {{Citation

| last = Sokal

| first = Alan D.

| editor-last = Webb

| editor-first = Bridget S.

| contribution = The multivariate Tutte polynomial (alias Potts model) for graphs and matroids

| title = Surveys in Combinatorics

| volume = 327

| pages = 173–226

| year = 2005

| series = London Mathematical Society Lecture Note Series

| publisher = Cambridge University Press

| doi = 10.1017/CBO9780511734885.009

| arxiv = math/0503607

| isbn = 978-0-521-61523-5

}}.

• {{Citation

| last = Tutte

| first = W. T.

| author-link = William Thomas Tutte

| title = Graph Theory

| publisher = Cambridge University Press

| year = 2001

| isbn = 978-0521794893

}}.

• {{Citation

| last = Tutte

| first = W. T.

| author-link = William Thomas Tutte

| title = Graph-polynomials

| journal = Advances in Applied Mathematics

| volume = 32

| issue = 1–2

| year = 2004

| pages = 5–9

| doi = 10.1016/S0196-8858(03)00041-1

| doi-access = free

}}.

• {{Citation

| last1 = Vertigan

| first1 = D. L.

| last2 = Welsh

| first2 = D. J. A.

| author-link2 = Dominic Welsh

| title = The Computational Complexity of the Tutte Plane: the Bipartite Case

| journal = Combinatorics, Probability and Computing

| volume = 1

| issue = 2

| pages = 181–187

| year = 1992

| doi = 10.1017/S0963548300000195

}}.

• {{Citation

| last = Vertigan

| first = Dirk

| title = The Computational Complexity of Tutte Invariants for Planar Graphs

| journal = SIAM Journal on Computing

| volume = 35

| issue = 3

| pages = 690–712

| year = 2005

| doi = 10.1137/S0097539704446797

}}.

• {{Citation

| last = Welsh

| first = D. J. A.

| author-link = Dominic Welsh

| title = Matroid Theory

| publisher = Academic Press

| year = 1976

| isbn = 012744050X

}}.

• {{Citation

| last = Welsh

| first = Dominic

| author-link = Dominic Welsh

| title = Complexity: Knots, Colourings and Counting

| series = London Mathematical Society Lecture Note Series

| year = 1993

| publisher = Cambridge University Press

| isbn = 978-0521457408

}}.

• {{Citation

| last = Welsh

| first = Dominic

| author-link = Dominic Welsh

| title = The Tutte polynomial

| journal = Random Structures & Algorithms

| volume = 15

| issue = 3–4

| pages = 210–228

| year = 1999

| publisher = Wiley

| issn = 1042-9832

| doi = 10.1002/(SICI)1098-2418(199910/12)15:3/4<210::AID-RSA2>3.0.CO;2-R

}}.

• {{Citation

| last1 = Welsh

| first1 = D. J. A.

| authorlink1 = Dominic Welsh

| last2 = Merino

| first2 = C.

| title = The Potts model and the Tutte polynomial

| journal = Journal of Mathematical Physics

| volume = 41

| issue = 3

| pages = 1127–1152

| year = 2000

| doi = 10.1063/1.533181

| bibcode = 2000JMP....41.1127W

}}.

• {{Citation

| last = Wilf

| first = Herbert S.

| authorlink = Herbert Wilf

| title = Algorithms and complexity

| publisher = Prentice Hall

| year = 1986

| isbn = 0-13-021973-8

| url = https://www.math.upenn.edu/~wilf/AlgoComp.pdf

| mr = 897317

}}.

{{refend}}

• {{springer|title=Tutte polynomial|id=p/t120210}}
• {{MathWorld | urlname=TuttePolynomial| title=Tutte polynomial}}
• PlanetMath [https://planetmath.org/ChromaticPolynomial Chromatic polynomial]
• Steven R. Pagano: [https://web.archive.org/web/20060202005537/http://www.ms.uky.edu/~pagano/Matridx.htm Matroids and Signed Graphs]
• Sandra Kingan: [https://web.archive.org/web/20060211053237/http://members.aol.com/matroids/ Matroid theory]. Many links.
• Code for computing Tutte, Chromatic and Flow Polynomials by Gary Haggard, David J. Pearce and Gordon Royle: [https://whileydave.com/projects/tutte/]

Category:Computational problems

Category:Duality theories

Category:Matroid theory

Category:Polynomials

Category:Graph invariants