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
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 .
Keywords: Chip firing game, Tutte polynomial, graph
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.