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 (22)

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

This page was built for publication: Sinks in acyclic orientations of graphs