Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)



Tutte polynomials and link polynomials

Author: François Jaeger
Journal: Proc. Amer. Math. Soc. 103 (1988), 647-654
MSC: Primary 57M25; Secondary 05C10, 57M15
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.

References [Enhancements On Off] (What's this?)

  • [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)

Similar Articles

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

Article copyright: © Copyright 1988 American Mathematical Society

American Mathematical Society