Sinks in acyclic orientations of graphs

DOI10.1006/JCTB.2000.1975zbMATH Open1023.05069arXivmath/9907078OpenAlexW1986881475MaRDI QIDQ1850490FDOQ1850490

David D. Gebhard, Bruce E. Sagan

Publication date: 10 December 2002

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/math/9907078

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

zbMATH Keywords

algorithmchromatic polynomialinductionbeta invariant

Mathematics Subject Classification ID

Directed graphs (digraphs), tournaments (05C20) Coloring of graphs and hypergraphs (05C15)

Cites Work

• A symmetric function generalization of the chromatic polynomial of a graph
• On the Interpretation of Whitney Numbers Through Arrangements of Hyperplanes, Zonotopes, Non-Radon Partitions, and Orientations of Graphs
• Acyclic orientations of graphs
• 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
• A higher invariant for matroids
• Parallel concepts in graph theory
• A chromatic symmetric function in noncommuting variables
• Title not available (Why is that?)
• A Rogers-Ramanujan bijection
• Bijective proofs of two broken circuit theorems
• On the Foundations of Combinatorial Theory. VII: Symmetric Functions through the Theory of Distribution and Occupancy

Cited In (25)

• 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
• A chromatic symmetric function in noncommuting variables
• Title not available (Why is that?)
• A bijection for Eulerian-equivalence classes of totally cyclic orientations
• Baxter permutations and plane bipolar orientations
• Title not available (Why is that?)
• 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
• Toppleable permutations, excedances and acyclic orientations

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)