Abstract: 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.
Recommendations
- Acyclic orientations of graphs. (Reprint)
- scientific article; zbMATH DE number 3859153
- Acyclic orientations and monotonicity in graphs
- The connectivity of acyclic orientation graphs
- scientific article; zbMATH DE number 1439424
- Acyclic orientations of random graphs
- Searching for acyclic orientations of graphs
- Acyclic orientations of complete bipartite graphs
- Acyclic and Totally Cyclic Orientations in Planar Graphs
Cites work
- scientific article; zbMATH DE number 867661 (Why is no real title available?)
- A Rogers-Ramanujan bijection
- A chromatic symmetric function in noncommuting variables
- A higher invariant for matroids
- A symmetric function generalization of the chromatic polynomial of a graph
- Acyclic orientations of graphs
- Bijective proofs of two broken circuit theorems
- Graph colorings and related symmetric functions: ideas and applications: A description of results, interesting applications, and notable open problems.
- Noncommutative Schur functions and their applications
- Noncommutative symmetric functions
- On the Foundations of Combinatorial Theory. VII: Symmetric Functions through the Theory of Distribution and Occupancy
- On the Interpretation of Whitney Numbers Through Arrangements of Hyperplanes, Zonotopes, Non-Radon Partitions, and Orientations of Graphs
- Parallel concepts in graph theory
Cited in
(25)- Toppleable permutations, excedances and acyclic orientations
- Some new characterizations of graph colorability and of blocking sets of projective spaces
- Asymptotic behavior of acyclic and cyclic orientations of directed lattice graphs
- The Hopf algebra of uniform block permutations.
- \(G\)-parking functions, acyclic orientations and spanning trees
- Zero-free regions for multivariate tutte polynomials (alias Potts-model partition functions) of graphs and matroids
- Acyclic orientations and the chromatic polynomial
- A geometric approach to acyclic orientations
- Activity preserving bijections between spanning trees and orientations in graphs
- Criterion for a graph to admit a good orientation in terms of leaf blocks
- The topology of the coloring complex
- scientific article; zbMATH DE number 3859153 (Why is no real title available?)
- A chromatic symmetric function in noncommuting variables
- A bijection for Eulerian-equivalence classes of totally cyclic orientations
- Baxter permutations and plane bipolar orientations
- scientific article; zbMATH DE number 637327 (Why is no real title available?)
- Set maps, umbral calculus, and the chromatic polynomial
- Sink-Stable Sets of Digraphs
- Acyclic orientation polynomials and the sink theorem for chromatic symmetric functions
- Acyclic orientation polynomials and the sink theorem for chromatic symmetric functions
- Proving a conjecture on chromatic polynomials by counting the number of acyclic orientations
- Study of exponential growth constants of directed heteropolygonal Archimedean lattices
- The active bijection for graphs
- Combinatorial properties of poly-Bernoulli relatives
- Acyclic orientations on the Sierpinski gasket
This page was built for publication: Sinks in acyclic orientations of graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1850490)
