SpringerLink
Log in

Graph Polynomials and Their Applications I: The Tutte Polynomial

  • Chapter
  • First Online:
Structural Analysis of Complex Networks

Abstract

In this survey of graph polynomials, we emphasize the Tutte polynomial and a selection of closely related graph polynomials such as the chromatic, flow, reliability, and shelling polynomials. We explore some of the Tutte polynomial’s many properties and applications and we use the Tutte polynomial to showcase a variety of principles and techniques for graph polynomials in general. These include several ways in which a graph polynomial may be defined and methods for extracting combinatorial information and algebraic properties from a graph polynomial. We also use the Tutte polynomial to demonstrate how graph polynomials may be both specialized and generalized, and how they can encode information relevant to physical applications. We conclude with a brief discussion of computational complexity considerations.

MSC2000: Primary 05-02; Secondary 05C15, 05A15, 05C99

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
EUR 32.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or Ebook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
EUR 29.95
Price includes VAT (Germany)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
EUR 139.09
Price includes VAT (Germany)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Hardcover Book
EUR 181.89
Price includes VAT (Germany)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free ship** worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. Aigner M, Ziegler GM (2001) Proofs from the book. Springer, Berlin, Heidelberg

    MATH  Google Scholar 

  2. Alon N, Frieze AM, Welsh DJA (1995) Polynomial time randomized approximation schemes for Tutte–Gröthendieck invariants: the dense case. Random Struct Algorithm 6:459–478

    Article  MATH  MathSciNet  Google Scholar 

  3. Andrzejak A (1998) An algorithm for the Tutte polynomials of graphs of bounded treewidth. Discrete Math 190:39–54

    Article  MATH  MathSciNet  Google Scholar 

  4. Bak P, Tang C, Wiesenfeld K (1988) Self-organized criticality. Phys Rev A 38:364–374

    Article  MathSciNet  Google Scholar 

  5. Benashski J, Martin R, Moore J, Traldi L (1995) On the β-invariant for graphs. Congr Numer 109:211–221

    MATH  MathSciNet  Google Scholar 

  6. Biggs N (1996) Algebraic graph theory, 2nd edn. Cambridge University Press, Cambridge

    Google Scholar 

  7. Biggs N (1996) Chip firing and the critical group of a graph. Research report, London school of economics, London

    Google Scholar 

  8. Birkhoff GD (1912) A determinant formula for the number of ways of coloring a map. Ann Math 14:42–46

    Article  MathSciNet  Google Scholar 

  9. Björner A (1992) Homology and shellability of matroids and geometric lattices. In: White N (ed) Matroid applications, encyclopedia of mathematics and its applications. Cambridge University Press, Cambridge

    Google Scholar 

  10. Bodlaender HL (1993) A tourist guide through treewidth. Acta Cybernet 11:1–21

    MATH  MathSciNet  Google Scholar 

  11. Bollobás B (1998) Modern graph theory. Graduate texts in mathematics. Springer, New York

    MATH  Google Scholar 

  12. Borgs C (2006) Absence of zeros for the chromatic polynomial on bounded degree graphs. Combinator Probab Comput 15:63–74

    Article  MATH  MathSciNet  Google Scholar 

  13. Brown JI, Hickman CA, Sokal AD, Wagner DG (2001) On the chromatic roots of generalized theta graphs. J Combin Theory B 83:272–297

    Article  MATH  MathSciNet  Google Scholar 

  14. Brylawski T (1971) A combinatorial model for series–parallel networks. Trans Am Math Soc 154:1–22

    MATH  MathSciNet  Google Scholar 

  15. Brylawski T (1972) A decomposition for combinatorial geometries. Trans Am Math Soc 171:235–282

    MATH  MathSciNet  Google Scholar 

  16. Brylawski T (1982) The Tutte polynomial, Part 1: general theory. In: Barlotti A (ed) Matroid theory and its applications. Proceedings of the 3rd international mathematical summer center (C.I.M.E. 1980)

    Google Scholar 

  17. Brylawski T, Oxley J (1992) The Tutte polynomial and its applications. In: White N (ed) Matroid applications, encyclopedia of mathematics and its applications. Cambridge University Press, Cambridge

    Google Scholar 

  18. Chang SC, Shrock R (2001) Exact Potts model partition functions on wider arbitrary-length strips of the square lattice. Physica A 296:234–288

    Article  MATH  MathSciNet  Google Scholar 

  19. Chang SC, Jacobsen J, Salas J, Shrock R (2004) Exact Potts model partition functions for strips of the triangular lattice. J Stat Phys 114:768–823

    Article  MathSciNet  Google Scholar 

  20. Chari MK, Colbourn CJ (1997) Reliability polynomials: a survey. J Combin Inf System Sci 22:177–193

    MATH  MathSciNet  Google Scholar 

  21. Chia GL (1997) A bibliography on chromatic polynomials. Discrete Math 172:175–191

    Article  MATH  MathSciNet  Google Scholar 

  22. Choe YB, Oxley JG, Sokal AD, Wagner DG (2004) Homogeneous multivariate polynomials with the half-plane property. Adv Appl Math 32:88–187

    Article  MATH  MathSciNet  Google Scholar 

  23. Crapo HH (1967) A higher invariant for matroids. J Combin Theory 2:406–417

    Article  MATH  MathSciNet  Google Scholar 

  24. Crapo HH (1969) The Tutte polynomial. Aeq Math 3:211–229

    Article  MATH  MathSciNet  Google Scholar 

  25. Dhar D (1990) Self-organized critical state of sandpile automaton models. Phys Rev Lett 64:1613–1616

    Article  MATH  MathSciNet  Google Scholar 

  26. Diestel R (2000) Graph theory. Graduate texts in mathematics. Springer, New York

    Google Scholar 

  27. Dong FM (2004) The largest non-integer zero of chromatic polynomials of graphs with fixed order. Discrete Math 282:103–112

    Article  MATH  MathSciNet  Google Scholar 

  28. Dong FM, Koh KM (2004) On upper bounds for real roots of chromatic polynomials. Discrete Math 282:95–101

    Article  MATH  MathSciNet  Google Scholar 

  29. Dong FM, Koh KM (2007) Bounds for the coefficients of flow polynomials. J Combin Theory B 97:413–420

    Article  MATH  MathSciNet  Google Scholar 

  30. Dong FM, Koh KM, Teo KL (2005) Chromatic polynomials and chromaticity of graphs. World Scientific, Hackensack, NJ

    Book  MATH  Google Scholar 

  31. Duffin RJ (1965) Topology of series–parallel networks. J Math Anal Appl 10:303–318

    Article  MATH  MathSciNet  Google Scholar 

  32. Ellis-Monaghan J (2004) Exploring the Tutte–Martin connection. Discrete Math 281:173–187

    Article  MATH  MathSciNet  Google Scholar 

  33. Ellis-Monaghan J (2004) Identities for the circuit partition polynomials, with applications to the diagonal Tutte polynomial. Adv Appl Math 32:188–197

    Article  MATH  MathSciNet  Google Scholar 

  34. Etienne G, Las Vergnas M (1998) External and internal elements of a matroid basis. Discrete Math 179:111–119

    Article  MATH  MathSciNet  Google Scholar 

  35. Farr GE (2006) The complexity of counting colourings of subgraphs of the grid. Combinator Probab Comput 15:377–383

    Article  MATH  MathSciNet  Google Scholar 

  36. Farr GE (2007) Tutte–Whitney polynomials: some history and generalizations. In: Grimmett GR, McDiarmid CJH (eds) Combinatorics, complexity, and chance: a tribute to Dominic Welsh. Oxford University Press, Oxford

    Google Scholar 

  37. Fernandez R, Procacci A (2008) Regions without complex zeros for chromatic polynomials on graphs with bounded degree. Combinator Probab Comput 17:225–238

    MATH  MathSciNet  Google Scholar 

  38. Gabrielov A (1993) Abelian avalanches and the Tutte polynomials. Physica A 195:253–274

    Article  MathSciNet  Google Scholar 

  39. Garey MR, Johnson DS (1979) Computers and intractability – a guide to the theory of NP-completeness. W.H. Freeman, San Francisco

    Google Scholar 

  40. Gioan E (2007) Enumerating degree sequences in digraphs and a cycle–cocycle reversing system. Eur J Combinator 28:1351–1366

    Article  MATH  MathSciNet  Google Scholar 

  41. Gioan E, Las Vergnas M (2005) Activity preserving bijections between spanning trees and orientations in graphs. Discrete Math 298:169–188

    Article  MATH  MathSciNet  Google Scholar 

  42. Gioan E, Las Vergnas M (2007) On the evaluation at (j, j 2) of the Tutte polynomial of a ternary matroid. J Algebr Combinator 25:1–6

    Article  MATH  MathSciNet  Google Scholar 

  43. Goldberg LA, Jerrum MR (2007) Inapproximability of the Tutte polynomial. In STOC ’07: Proceedings of the 39th annual ACM symposium on theory of computing. ACM Press, New York

    Google Scholar 

  44. Green C, Zaslavsky T (1983) On the interpretation of whitney numbers through arrangements of hyperplanes, zonotopes, non-radon partitions and orientations of graphs. Trans Am Math Soc 280:97–126

    Google Scholar 

  45. Jackson B (1993) A zero-free interval for chromatic polynomials of graphs. Combinator Probab Comput 2:325–336

    MATH  Google Scholar 

  46. Jackson B (2003) Zeros of chromatic and flow polynomials of graphs. J Geom. 76:95–109

    MATH  MathSciNet  Google Scholar 

  47. Jackson B (2007) Zero-free intervals for flow polynomials of near-cubic graphs. Combinator Probab Comput 16:85–108

    Article  MATH  Google Scholar 

  48. Jaeger F (1976) On nowhere-zero flows in multigraphs. In: Nash-Williams Crispin St JA, Sheehan J (eds) Proceedings of the 5th British combinatorial conference, Winnipeg

    Google Scholar 

  49. Jaeger F (1988) Nowhere-zero flow problems. In: Beineke LW, Wilson RJ (eds) Selected topics in graph theory, vol 3. Academic, New York

    Google Scholar 

  50. Jaeger F, Vertigan DL, Welsh DJA (1990) On the computational complexity of the Jones and Tutte polynomials. Math Proc Cambridge Philos Soc 108:35–53

    Article  MATH  MathSciNet  Google Scholar 

  51. Jerrum MR, Sinclair A (1993) Polynomial time approximation algorithms for the Ising model. SIAM J Comput 22:1087–1116

    Article  MATH  MathSciNet  Google Scholar 

  52. Kasteleyn PW (1961) The statistics of dimers on a lattice. Physica 27:1209–1225

    Article  Google Scholar 

  53. Kleitman DJ, Winston KJ (1981) Forests and score vectors. Combinatorica 1:49–54

    Article  MATH  MathSciNet  Google Scholar 

  54. Kook W, Reiner V, Stanton D (1999) A convolution formula for the Tutte polynomial. J Combin Theory B 76:297–300

    Article  MATH  MathSciNet  Google Scholar 

  55. Las Vergnas M (1977) Acyclic and totally cyclic orientations of combinatorial geometries. Discrete Math 20:51–61

    Article  MathSciNet  Google Scholar 

  56. Las Vergnas M (1984) The Tutte polynomial of a morphism of matroids II. Activities of orientations. In: Bondy JA, Murty USR (eds) Progress in graph theory, Proceedings of Waterloo Silver Jubilee Combinatorial Conference 1982. Academic, Toronto

    Google Scholar 

  57. Las Vergnas M (1988) On the evaluation at (3,3) of the Tutte polynomial of a graph. J Combin Theory B 44:367–372

    Article  Google Scholar 

  58. Las Vergnas M. The Tutte polynomial of a morphism of matroids V. Derivatives as generating functions, Preprint

    Google Scholar 

  59. Lieb EH (1967) Residual entropy of square ice. Phys Rev 162:162–172

    Article  Google Scholar 

  60. Makowsky JA (2005) Colored Tutte polynomials and Kauffman brackets for graphs of bounded tree width. Discrete Appl Math 145:276–290

    Article  MATH  MathSciNet  Google Scholar 

  61. Makowsky JA, Rotics U, Averbouch I, Godlin B (2006) Computing graph polynomials on graphs of bounded clique-width. In: Lecture Notes in Computer Science 4271. Springer, New York

    Google Scholar 

  62. Martin P (1977) Enumérations eulériennes dans le multigraphs et invariants de Tutte–Gröthendieck. PhD thesis, Grenoble

    Google Scholar 

  63. Martin P (1978) Remarkable valuation of the dichromatic polynomial of planar multigraphs. J Combin Theory B 24:318–324

    Article  MATH  Google Scholar 

  64. McKee TA (2001) Recognizing dual-chordal graphs. Congr Numer 150:97–103

    MATH  MathSciNet  Google Scholar 

  65. Merino C (1997) Chip firing and the Tutte polynomial. Ann Combin 1:253–259

    Article  MATH  MathSciNet  Google Scholar 

  66. Merino C (2001) The chip firing game and matroid complex. Discrete Mathematics and Theoretical Computer Science, Proceedings, vol AA, pp 245–256

    Google Scholar 

  67. Merino C, de Mier A, Noy M (2001) Irreducibility of the Tutte polynomial of a connected matroid. J Combin Theory B 83:298–304

    Article  MATH  Google Scholar 

  68. Noble SD (1998) Evaluating the Tutte polynomial for graphs of bounded tree-width. Combinator Probab Comput 7:307–321

    Article  MATH  MathSciNet  Google Scholar 

  69. Noble SD (2007) The complexity of graph polynomials. In: Grimmett GR, McDiarmid CJH (eds) Combinatorics, complexity, and chance: a tribute to Dominic Welsh. Oxford University Press, Oxford

    Google Scholar 

  70. Oum S, Seymour PD (2006) Approximating clique-width and branch-width. J Combin Theory B 96:514–528

    Article  MATH  MathSciNet  Google Scholar 

  71. Oxley J (1982) On Crapo’s beta invariant for matroids. Stud Appl Math 66:267–277

    MATH  MathSciNet  Google Scholar 

  72. Oxley J, Welsh DJA (1979) The Tutte polynomial and percolation. In: Bondy JA, Murty USR (eds) Graph theory and related topics. Academic, London

    Google Scholar 

  73. Pauling L (1935) The structure and entropy of ice and of other crystals with some randomness of atomic arrangement. J Am Chem Soc 57:2680–2684

    Article  Google Scholar 

  74. Procacci A, Scoppola B, Gerasimov V (2003) Potts model on infinite graphs and the limit of chromatic polynomials. Commun Math Phys 235:215–231

    Article  MATH  MathSciNet  Google Scholar 

  75. Provan JS, Billera LJ (1980) Decompositions of simplicial complexes related to diameters of convex polyhedra. Math Oper Res 5:576–594

    Article  MATH  MathSciNet  Google Scholar 

  76. Read RC (1968) An introduction to chromatic polynomials. J Combin Theory B 4:52–71

    Article  MathSciNet  Google Scholar 

  77. Read RC, Rosenstiehl P (1978) On the principal edge tripartition of a graph. Ann Discrete Math 3:195–226

    Article  MATH  MathSciNet  Google Scholar 

  78. Read RC, Royle G (1991) Chromatic roots of families of graphs. In: Alavi Y et al (eds) Graph theory, combinatorics, and applications. Wiley, New York

    Google Scholar 

  79. Robertson N, Seymour PD (1984) Graph minors. I. Excluding a forest. J Combin Theory B 35:39–61

    MathSciNet  Google Scholar 

  80. Robertson N, Seymour PD (1984) Graph minors. III. Planar tree-width. J Combin Theory B 36:49–64

    MATH  MathSciNet  Google Scholar 

  81. Robertson N, Seymour PD (1986) Graph minors. II. Algorithmic aspects of tree-width. J Algorithm 7:309–322

    MATH  MathSciNet  Google Scholar 

  82. Royle G (2007) Graphs with chromatic roots in the interval (1,2). Electron J Combinator 14(1):N18

    MathSciNet  Google Scholar 

  83. Royle G (2008) Planar triangulations with real chromatic roots arbitrarily close to four. Ann Combinator 12:195–210

    Article  MATH  MathSciNet  Google Scholar 

  84. Schwärzler W (1993) The coefficients of the Tutte polynomial are not unimodal. J Combin Theory B 58:240–242

    Article  MATH  Google Scholar 

  85. Sekine K, Imai H, Tani S (1995) Computing the Tutte polynomial of a graph of moderate size. In: Lecture Notes in Computer Science. Springer, Berlin

    Google Scholar 

  86. Seymour PD (1981) Nowhere-zero 6-flows. J Combin Theory B, 30, 130–135

    Article  MATH  MathSciNet  Google Scholar 

  87. Seymour PD, Welsh DJA (1975) Combinatorial applications of an inequality of statistical mechanics. Math Proc Cambridge Philos Soc 77:485–495

    Article  MATH  MathSciNet  Google Scholar 

  88. Shrock R, Tsai SH (1997) Asymptotic limits and zeros of chromatic polynomials and ground state entropy of Potts antiferromagnets. Phys Rev E 55:5165–5179

    Article  Google Scholar 

  89. Shrock R, Tsai SH (1997) Families of graphs with W r (G, q) functions that are nonanalytic at \(1/q = 0\). Phys Rev E 56:3935–3943

    Article  MathSciNet  Google Scholar 

  90. Shrock R, Tsai SH (1998) Ground state entropy of Potts antiferromagnets: cases with noncompact W boundaries having multiple points at \(1/q = 0\). Physica A 259:315–348

    Article  Google Scholar 

  91. Shrock R (2001) Chromatic polynomials and their zeros and asymptotic limits for families of graphs. Discrete Math 231:421–446

    Article  MATH  MathSciNet  Google Scholar 

  92. Sokal AD (2001) A personal list of unsolved problems concerning lattice gases and antiferromagnetic Potts models. Markov Process Relat Fields 7:21–38

    MATH  MathSciNet  Google Scholar 

  93. Sokal AD (2001) Bounds on the complex zeros of (di)chromatic polynomials and Potts-model partition functions. Combinator Probab Comput 10:41–77

    MATH  MathSciNet  Google Scholar 

  94. Sokal AD (2004) Chromatic roots are dense in the whole complex plane. Combinator Probab Comput 13:221–261

    Article  MATH  MathSciNet  Google Scholar 

  95. Stanley R (1973) Acyclic orientations of graphs. Discrete Math 5:171–178

    Article  MATH  MathSciNet  Google Scholar 

  96. Stanley R (1980) Decomposition of rational polytopes. Ann Discrete Math 6:333–342

    Article  MathSciNet  Google Scholar 

  97. Stanley R (1996) Combinatorics and commutative algebra, 2nd edn. Progress in Mathematics, vol 41. Birkhäuser, Boston Besel Stuttgart

    Google Scholar 

  98. Stanley R (1996) Enumerative combinatorics, vol 1. Cambridge University Press, Cambridge

    Google Scholar 

  99. Stanley R (1999) Enumerative combinatorics, vol 2. Cambridge University Press, Cambridge

    Google Scholar 

  100. Thomassen C (1997) The zero-free intervals for chromatic polynomials of graphs. Combinator Probab Comput 6:497–506

    Article  MATH  MathSciNet  Google Scholar 

  101. Traldi L (2006) On the colored Tutte polynomial of a graph of bounded treewidth. Discrete Appl Math 154:1032–1036

    Article  MATH  MathSciNet  Google Scholar 

  102. Tutte WT (1947) A ring in graph theory. Proc Cambridge Philos Soc 43:26–40

    Article  MATH  MathSciNet  Google Scholar 

  103. Tutte WT (1948) An algebraic theory of graphs, PhD thesis, University of Cambridge

    Google Scholar 

  104. Tutte WT (1954) A contribution to the theory of chromatic polynomials. Can J Math 6:80–91

    MATH  MathSciNet  Google Scholar 

  105. Tutte WT (1967) On dichromatic polynomials. J Combin Theory 2:301–320

    Article  MATH  MathSciNet  Google Scholar 

  106. Tutte WT (1984) Graph theory. Cambridge University Press, Cambridge

    MATH  Google Scholar 

  107. Tutte WT (2004) Graph-polynomials. Special issue on the Tutte polynomial. Adv Appl Math 32:5–9

    MATH  MathSciNet  Google Scholar 

  108. Vertigan D (1998) Bicycle dimension and special points of the Tutte polynomial. J Combin Theory B 74:378–396

    Article  MATH  MathSciNet  Google Scholar 

  109. Vertigan DL, Welsh DJA (1992) The computational complexity of the Tutte plane: the bipartite case. Combinator Probab Comput 1:181–187

    MATH  MathSciNet  Google Scholar 

  110. Welsh DJA (1993) Complexity: knots, colorings and counting. Cambridge University Press, Cambridge

    Google Scholar 

  111. Welsh DJA (1999) The Tutte polynomial, in statistical physics methods in discrete probability, combinatorics, and theoretical computer science. Random Struct Algorithm 15:210–228

    Article  MATH  MathSciNet  Google Scholar 

  112. Welsh DJA, Merino C (2000) The Potts model and the Tutte polynomial. J Math Phys 41:1127–1152

    Article  MATH  MathSciNet  Google Scholar 

  113. Whitney H (1932) A logical expansion in mathematics. Bull Am Math Soc 38:572–579

    Article  MathSciNet  Google Scholar 

  114. Woodall D (1992) A zero-free interval for chromatic polynomials. Discrete Math 101: 333–341

    Article  MATH  MathSciNet  Google Scholar 

  115. Yetter D (1990) On graph invariants given by linear recurrence relations. J Combin Theory B 48:6–18

    Article  MATH  MathSciNet  Google Scholar 

  116. Zaslavsky T (1975) Facing up to arrangements: face-count formulas for partitions of space by hyperplanes. Mem Am Math Soc 154. American Mathematical Society, Providence, RI

    Google Scholar 

  117. Zaslavsky T (1987) The Möbius function and the characteristic polynomial. In: White N (ed) Combinatorial geometries, encyclopedia of mathematics and its applications. Cambridge University Press, Cambridge

    Google Scholar 

  118. Zhang CQ (1997) Integer flows and cycle covers of graphs. Marcel Dekker Inc., New York

    Google Scholar 

Download references

Acknowledgments

We thank all the friends and colleagues who offered many helpful comments and suggestions during the writing of this chapter.

The first author was supported by the National Security Agency and by the Vermont Genetics Network through Grant Number P20 RR16462 from the INBRE Program of the National Center for Research Resources (NCRR), a component of the National Institutes of Health (NIH).

The second author was supported by CONACYT of Mexico, Grant 83977.

Author information

Authors and Affiliations

  1. Department of Mathematics, Saint Michael’s College, One Winooski Park, Colchester, VT, 05439, USA

    Joanna A. Ellis-Monaghan

  2. Department of Mathematics and Statistics, University of Vermont, 16 Colchester Avenue, Burlington, VT, 05405, USA

    Joanna A. Ellis-Monaghan

Authors
  1. Joanna A. Ellis-Monaghan
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Criel Merino
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Joanna A. Ellis-Monaghan .

Editor information

Editors and Affiliations

  1. Medizinische Informatik und Technik, Institute for Bioinformatics and Transla, UMIT-Private Universität für Gesundheits, Eduard Wallnöfer-Zentrum 1, Hall in Tirol, A-6060, Austria

    Matthias Dehmer

Rights and permissions

Reprints and permissions

Copyright information

© 2011 Springer Science+Business Media, LLC

About this chapter

Cite this chapter

Ellis-Monaghan, J.A., Merino, C. (2011). Graph Polynomials and Their Applications I: The Tutte Polynomial. In: Dehmer, M. (eds) Structural Analysis of Complex Networks. Birkhäuser Boston. https://doi.org/10.1007/978-0-8176-4789-6_9

Download citation

Publish with us

Policies and ethics

Search

Navigation