Annals of Combinatorics 1 (1997) 253-259


Chip Firing and the Tutte Polynomial

Criel Merino López

Mathematical Institute, Oxford University, Oxford OX1 2HP, UK
merino@maths.ox.ac.uk

Received May 30, 1997

AMS Subject Classification: 05C99, 05E99, 90D43

Abstract. It is shown that the generating function of critical configurations of a version of a chip firing game on a graph G is an evaluation of the Tutte polynomial of G, thus proving a conjecture of Biggs [3].

Keywords: Chip firing game, Tutte polynomial, graph


References

1.  N. Biggs, Chip firing and the critical group of a graph, CDAM Research Report Series, LSE-CDAM-96-03, January 1996.

2.  N. Biggs and P. Winkler, Chip-firing and the chromatic polynomial, CDAM Research Report Series, LSE-CDAM-97-03, February 1997.

3.  N. Biggs, Combinatorial Theory Seminar, Mathematical Institute, Oxford University, February 1997.

4.  A. Bjòrner and L. Lovàsz, Chip-firing game on directed graphs, J. Algebraic Combin. 1 (1992) 305–328.

5.  A. Björner, L. Lovàsz, and P.W. Shor, Chip-firing game on graphs, Europ. J. Combin. 12 (1991) 283–291.

6.  D.J.A. Welsh, Complexity: knots, colourings and counting, In: London Mathematical Society, Lecture Note Series 186, Cambridge University Press, 1993, pp. 42–48.


Get the LaTex | DVI | PS file of this abstract.

back