Proceedings of the American Mathematical Society
American Mathematical Society
In this paper we study the equivalence relation on the set of acyclic orientations of a graph Y that arises through source-to-sink conversions. This source-to-sink conversion encodes, e.g. conjugation of Coxeter elements of a Coxeter group. We give a direct proof of a recursion for the number of equivalence classes of this relation for an arbitrary graph Y using edge deletion and edge contraction of non-bridge edges. We conclude by showing how this result may also be obtained through an evaluation of the Tutte polynomial as T (Y, 1, 0), and we provide bijections to two other classes of acyclic orientations that are known to be counted in the same way. A transversal of the set of equivalence classes is given.
Please use the publisher's recommended citation. http://www.ams.org/journals/proc/2008-136-12/S0002-9939-08-09543-9/