Sinks in Acyclic Orientations of Graphs
Sinks in Acyclic Orientations of Graphs
复制标题
DOI：
10.1006/jctb.2000.1975
复制
发表时间：
1999-07
期刊：
影响因子：
--
通讯作者：
D. Gebhard;B. Sagan
中科院分区：
文献类型：
--
作者：
D. Gebhard;B. Sagan
Greene和Zaslavsky证明了在给定顶点有唯一汇聚的图G的无环取向的数目，不超过符号，是色多项式的线性系数。我们用纯归纳法、非交换对称函数和算法双射给出了这一结果的三个证明。我们也证明了他们的结果，如果e=u0v0是G的一条边，那么在u0处有唯一源和v0处有唯一汇的无环方向的数目是Crapo的不变量。
Greene and Zaslavsky proved that the number of acyclic orientations of a graph G with a unique sink at a given vertex is, up to sign, the linear coefficient of the chromatic polynomial. We give three proofs of this result using pure induction, noncommutative symmetric functions, and an algorithmic bijection. We also prove their result that if e=u0v0 is an edge of G then the number of acyclic orientations having a unique source at u0 and unique sink at v0 is Crapo's beta invariant.