Sinks in acyclic orientations of graphs

DOI10.1006/jctb.2000.1975zbMath1023.05069arXivmath/9907078OpenAlexW1986881475MaRDI QIDQ1850490

David D. Gebhard, Bruce E. Sagan

Publication date: 10 December 2002

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

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

zbMATH Keywords

algorithmchromatic polynomialinductionbeta invariant

Mathematics Subject Classification ID

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

Related Items

Toppleable permutations, excedances and acyclic orientations, Criterion for a graph to admit a good orientation in terms of leaf blocks, Proving a conjecture on chromatic polynomials by counting the number of acyclic orientations, Some new characterizations of graph colorability and of blocking sets of projective spaces, Set maps, umbral calculus, and the chromatic polynomial, The active bijection for graphs, Baxter permutations and plane bipolar orientations, \(G\)-parking functions, acyclic orientations and spanning trees, A chromatic symmetric function in noncommuting variables, Acyclic orientations and the chromatic polynomial, The topology of the coloring complex, Combinatorial properties of poly-Bernoulli relatives, Acyclic orientation polynomials and the sink theorem for chromatic symmetric functions, Acyclic orientation polynomials and the sink theorem for chromatic symmetric functions, A bijection for Eulerian-equivalence classes of totally cyclic orientations, The Hopf algebra of uniform block permutations., Asymptotic behavior of acyclic and cyclic orientations of directed lattice graphs, Study of exponential growth constants of directed heteropolygonal Archimedean lattices, Zero-free regions for multivariate tutte polynomials (alias Potts-model partition functions) of graphs and matroids, Activity preserving bijections between spanning trees and orientations in graphs, A geometric approach to acyclic orientations, ACYCLIC ORIENTATIONS ON THE SIERPINSKI GASKET

Cites Work

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