Sinks in Acyclic Orientations of Graphs
Loading...
Date
Authors
Journal Title
Journal ISSN
Volume Title
Publisher
Abstract
Description
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.
17 pages, 1 figure
17 pages, 1 figure