1999/07/12 by David D. Gebhard, Bruce E. Sagan
Mathematics · #math.CO #msc:05C20
published as J. Combin. Theory (B) 80 (2000) 130-146 · 17 pages, 1 figure
arxiv created 1999/07/12 · arxiv updated 2009/11/30
Greene and Zaslavsky proved that the number of acyclic orientations of a graph with a unique sink is, up to sign, the linear coefficient of the chromatic polynomial. We give three new proofs of this result using pure induction, noncommutative symmetric functions, and an algorithmic bijection.