Tutte polynomials and link polynomials

Author:
François Jaeger

Journal:
Proc. Amer. Math. Soc. **103** (1988), 647-654

MSC:
Primary 57M25; Secondary 05C10, 57M15

DOI:
https://doi.org/10.1090/S0002-9939-1988-0943099-0

MathSciNet review:
943099

Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We show how the Tutte polynomial of a plane graph can be evaluated as the "homfly" polynomial of an associated oriented link. Then we discuss some consequences for the partition function of the Potts model, the Four Color Problem and the time complexity of the computation of the homfly polynomial.

**[1]**K. Appel and W. Haken,*Every planar graph is four colorable*, Part I; W. Haken, K. Appel, and J. Koch,*Every planar graph is four colorable*, Part II, Illinois J. Math.**21**(1977), 429-567. MR**0543795 (58:27598d)****[2]**R. J. Baxter,*Exactly solved models in statistical mechanics*, Academic Press, New York, 1982. MR**690578 (86i:82002a)****[3]**C. Berge,*Graphes et hypergraphes*, Dunod, Paris, 1974. MR**0357171 (50:9639)****[4]**J. A. Bondy and U. S. R. Murty,*Graph theory with applications*, Macmillan, London, 1976. MR**0411988 (54:117)****[5]**J. H. Conway,*An enumeration of knots and links and some of their algebraic properties*, Computational Problems in Abstract Algebra, Pergamon Press, New York, 1970, pp. 329-358. MR**0258014 (41:2661)****[6]**J. R. Edmonds,*Pictures of knots and construction of planar triangulations*, Communication at the Third International Conference "Théorie des graphes et combinatoire," Marseille, June 1986.**[7]**P. Freyd, D. Yetter, J. Hoste, W. B. R. Lickorish, K. Millett, and A. Ocneanu,*A new polynomial invariant of knots and links*, Bull. Amer. Math. Soc. (N.S.)**12**(1985), 239-246. MR**776477 (86e:57007)****[8]**M. R. Garey and D. S. Johnson,*Computers and intractability: a guide to the theory of NPcompleteness*, Freeman, San Francisco, Calif., 1979. MR**519066 (80g:68056)****[9]**J. Hoste,*A polynomial invariant of knots and links*, Pacific J. Math.**124**(2) 1986, 295-320. MR**856165 (88d:57004)****[10]**V. F. R. Jones,*A polynomial invariant for knots via Von Neumann algebras*, Bull. Amer. Math. Soc. (N.S.)**12**(1985), 103-111. MR**766964 (86e:57006)****[11]**-,*A new knot polynomial and Von Neumann algebras*, Notices Amer. Math. Soc.**33**(1986), 219-225. MR**830613 (87d:57007)****[12]**L. H. Kauffman,*New invariants in the theory of knots*, preprint. MR**999974 (90e:57009)****[13]**-,*State models and the Jones polynomial*, Topology**26**(1987), 395-407. MR**899057 (88f:57006)****[14]**-,*Statistical mechanics and the Jones polynomial*, preprint.**[15]**-,*Formal knot theory*, Math. Notes 30, Princeton Univ. Press, Princeton, N.J., 1983. MR**712133 (85b:57006)****[16]**K. Murasugi,*Jones polynomials and classical conjectures in knot theory*, Topology**26**(1987), 187-194. MR**895570 (88m:57010)****[17]**O. Ore,*The four-color problem*, Academic Press, New York, 1967. MR**0216979 (36:74)****[18]**H. N. V. Temperley and E. H. Lieb,*Relations between the percolation and colouring problem and other graph-theoretical problems associated with regular plane lattices: some exact results for the percolation problem*, Proc. Roy. Soc. London**322A**(1971), 251-280. MR**0498284 (58:16425)****[19]**M. Thistlethwaite,*A spanning tree expansion of the Jones polynomial*, Topology**26**(1987), 297-309. MR**899051 (88h:57007)****[20]**W. T. Tutte,*A ring in graph theory*, Proc. Cambridge Philos. Soc.**43**(1947), 26-40. MR**0018406 (8:284k)****[21]**-,*A contribution to the theory of chromatic polynomials*, Canad. J. Math.**6**(1954), 80-91. MR**0061366 (15:814c)**

Retrieve articles in *Proceedings of the American Mathematical Society*
with MSC:
57M25,
05C10,
57M15

Retrieve articles in all journals with MSC: 57M25, 05C10, 57M15

Additional Information

DOI:
https://doi.org/10.1090/S0002-9939-1988-0943099-0

Article copyright:
© Copyright 1988
American Mathematical Society