\magnification=1440
\font\bigtenrm=cmr10 scaled\magstep4
Abstract for 
Ira M. Gessel and Bruce E. Sagan,
The Tutte Polynomial of a Graph, Depth-first Search

One of the most important numerical quantities that can be computed
from a graph $G$
is the two-variable Tutte polynomial.
Specializations of the Tutte polynomial count various
objects associated with $G$, e.g., subgraphs, spanning
trees, acyclic
orientations, inversions and parking functions.
We show that by partitioning certain
simplicial complexes related to $G$ into intervals,
one can provide combinatorial
demonstrations of these results.  One of the primary tools for
providing such a partition is depth-first search.




\bye

.
