<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 12 Issue 1" %>
Preface: Old and New Perspectives on the Tutte Polynomial
Joseph P.S. Kung
Department of Mathematics, University of North Texas, Denton, TX 76203, USA
Annals of Combinatorics 12 (2) p.133-137 June, 2008
AMS Subject Classification: 05C15; 05B35
This paper introduces a special issue on the Tutte polynomial derived from the Second Workshop on Tutte Polynomials and Applications, 2005, held at the Centre de Recerca Matem\`{a}tica,
Bellaterra, Catalonia. We discuss the prehistory of Tutte polynomials and two current areas of research, to what extent a graph is determined by its chromatic or Tutte polynomial and generic versions of Tutte polynomials.
Keywords: Tutte polynomial, graphs, matroids


1. G.D. Birkhoff, A determinant formula for the number of ways of coloring a map, Ann. of Math. (2) 14 (1-4) (1912/13) 42–46.

2. B. Bollob´as, L. Pebody, and O. Riordan, Contraction-deletion invariants for graphs, J. Combin. Theory Ser. B 80 (2) (2000) 320–345.

3. T. Brylawski and J.G. Oxley, The Tutte polynomial and its applications, In: Matroid Applications, N.L. White Ed., Cambridge Univ. Press, Cambridge, (1992) pp. 123–225.

4. P. Erdos, L. Lov´asz, and J. Spencer, Strong independence of graphcopy functions, In: Graph Theory and Related Topics, Academic Press, New York, (1979) pp. 165–172.

5. G.E. Farr, Tutte-Whitney polynomials: some history and generalizations, In: Combinatorics, Complexity and Chance: A Tribute to Dominic Welsh, G. Grimmett and C. MacDiarmid, Eds., Oxford Univ. Press, Oxford, (2007) pp. 28–52.

6. R.M. Foster, The Foster Census, Charles Babbage Research Centre, Winnipeg, Manitoba, 1988.

7. C.M. Fortuin and P.W. Kasteleyn, On the random-cluster model. I. Introduction and relations to other models, Physica 57 (4) (1972) 536–564.

8. W.H. Haemers and E. Spence, Enumeration of cospectral graphs, Europ. J. Combin. 25 (2) (2004) 199–211.

9. J.P.S. Kung, Twelve views of matroid theory, In: Combinatorial & Computational Mathematics (Pohang 2000), S. Hong, J.H. Kwak, K.H. Kim, and F.W. Roush, Eds., World Scienti fic, River Edge, NJ, (2001) pp. 56–96.

10. M. Noy, Graphs determined by polynomial invariants, Theoret. Comput. Sci. 307 (2) (2003) 365–384.

11. P. Orlik and L. Solomon, Combinatorics and topology of complements of hyperplanes, Invent. Math. 56 (2) (1980) 167–189.

12. R.C. Read and W.T. Tutte, Chromatic Polynomials, In: Selected Topics in Graph Theory, Vol. 3, L.W. Beineke and R.J. Wilson, Eds., Academic Press, San Diego, CA, (1988) pp. 15–42.

13. R.C. Read and E.G. Whitehead, The Tutte polynomial for homeomorphism classes of graphs, Discrete Math. 243 (1-3) (2002) 267–272.

14. L. Traldi, A dichromatic polynomial for weighted graphs and link polynomials, Proc. Amer. Math. Soc. 106 (1) (1989) 279–286.

15. W.T. Tutte, Graph Theory as I Have Known It, Oxford Univ. Press, New York, 1998.

16. W.T. Tutte, Graph-polynomials, Adv. Appl. Math. 32 (1-2) (2004) 5–9.

17. A.D. Sokal, The multivariate Tutte polynomial (alias Potts model) for graphs and matroids, In: Surveys in Combinatorics 2005, Cambridge Univ. Press, Cambridge, (2005) pp. 173– 226.

18. H. Whitney, The coloring of graphs, Ann. of Math. 33 (2) (1932) 688–718.