arXiv Analytics

Sign in

arXiv:math/9907078 [math.CO]AbstractReferencesReviewsResources

Sinks in Acyclic Orientations of Graphs

David D. Gebhard, Bruce E. Sagan

Published 1999-07-12Version 1

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.

Comments: 17 pages, 1 figure
Journal: J. Combin. Theory (B) 80 (2000) 130-146
Categories: math.CO
Subjects: 05C20
Related articles: Most relevant | Search more
arXiv:1902.02240 [math.CO] (Published 2019-02-06)
Chromatic Polynomial and Heaps of Pieces
arXiv:0907.0046 [math.CO] (Published 2009-07-01)
A geometric approach to acyclic orientations
arXiv:1803.08658 [math.CO] (Published 2018-03-23, updated 2020-07-10)
Proof of Lundow and Markström's conjecture on chromatic polynomials via novel inequalities

Links

Toolbox