Acyclic orientations of graphs
From MaRDI portal
Publication:2559389
DOI10.1016/0012-365X(73)90108-8zbMath0258.05113WikidataQ55892823 ScholiaQ55892823MaRDI QIDQ2559389
Publication date: 1973
Published in: Discrete Mathematics (Search for Journal in Brave)
Enumeration in graph theory (05C30) Coloring of graphs and hypergraphs (05C15) Directed graphs (digraphs), tournaments (05C20)
Related Items
The Broken-Circuit Complex, Properties of chromatic polynomials of hypergraphs not held for chromatic polynomials of graphs, On the Interpretation of Whitney Numbers Through Arrangements of Hyperplanes, Zonotopes, Non-Radon Partitions, and Orientations of Graphs, Toppleable permutations, excedances and acyclic orientations, On the Foundation of Combinatorial Theory. X. A Categorical Setting for Symmetric Functions, Hard Enumeration Problems in Geometry and Combinatorics, Sign-Coherent Identities for Characteristic Polynomials of Matroids, The drop polynomial of a weighted digraph, Associated \(r\)-Dowling numbers and some relatives, On the shape of a random acyclic digraph, Applications of multlinear algebra, Extremal graphs for the Tutte polynomial, Fourientation activities and the Tutte polynomial, Fourientations and the Tutte polynomial, Polynomial time randomized approximation schemes for Tutte–Gröthendieck invariants: The dense case, Dualities and reciprocities on graphs on surfaces, On enumeration and entropy of ribbon tilings, Hopf Monoids and Generalized Permutahedra, Proving a conjecture on chromatic polynomials by counting the number of acyclic orientations, On colorings and orientations of signed graphs, On maximum graphs in Tutte polynomial posets, Fully Optimal Bases and the Active Bijection in Graphs, Hyperplane Arrangements, and Oriented Matroids, Graph colorings and acyclic orientations, Interview with Xavier Viennot, Acyclic reorientation lattices and their lattice quotients, The chromatic generating function, A combinatorial link between labelled graphs and increasingly labelled Schröder trees, The work of June Huh, The birth of the strong components, COMBINATORIAL PROPERTIES FOR A CLASS OF SIMPLICIAL COMPLEXES EXTENDED FROM PSEUDO-FRACTAL SCALE-FREE WEB, The amazing chromatic polynomial, Counting acyclic and strong digraphs by descents, A deletion-contraction relation for the chromatic symmetric function, Generating functions of some families of directed uniform hypergraphs, Homology of Spaces of Directed Paths in Euclidean Pattern Spaces, Dual complementary polynomials of graphs and combinatorial-geometric interpretation on the values of Tutte polynomial at positive integers, A Hodge decomposition interpretation for the coefficients of the chromatic polynomial, New invariants for permutations, orders and graphs, Nowhere-harmonic colorings of graphs, The Hopf monoid and the basic invariant of directed graphs, The Potts model and the Tutte polynomial, Orbit-counting polynomials for graphs and codes, Combinatorial reciprocity theorems, On the number of upward planar orientations of maximal planar graphs, CHROMATIC POLYNOMIALS AND BIALGEBRAS OF GRAPHS, On the Broken-Circuit Complex of Graphs, Nowhere-zero \(\vec{k}\)-flows on graphs, A chromatic symmetric function in noncommuting variables, The coloring ideal and coloring complex of a graph, Acyclic orientations and the chromatic polynomial, Hopf algebras and the Penrose polynomial, Toric partial orders, Inside-out polytopes, Expansions of Chromatic Polynomials and Log-Concavity, Uniform random generation of large acyclic digraphs, Tutte polynomials for directed graphs, Combinatorial properties of poly-Bernoulli relatives, DISCRETE METRIC SPACES: STRUCTURE, ENUMERATION, AND 0-1 LAWS, Acyclic orientation polynomials and the sink theorem for chromatic symmetric functions, Acyclic orientation polynomials and the sink theorem for chromatic symmetric functions, Unnamed Item, Combinatorial Hopf Algebras of Simplicial Complexes, Study of exponential growth constants of directed heteropolygonal Archimedean lattices, Bijective Proofs of Proper Coloring Theorems, Unlabeled signed graph coloring, Bounds on the chromatic polynomial and on the number of acyclic orientations of a graph, Characteristic vertices of trees*, Characteristic vertices of trees*, Activity preserving bijections between spanning trees and orientations in graphs, Orientable hyperbolic 4-manifolds over the 120-cell, Acyclic Digraphs, A Linear Programming Construction of Fully Optimal Bases in Graphs and Hyperplane Arrangements, Combinatorial properties of Farey graphs, Weak Maps of Combinatorial Geometries, Transition polynomials, Enumerating colorings, tensions and flows in cell complexes, ACYCLIC ORIENTATIONS ON THE SIERPINSKI GASKET, Chromatic polynomials of graphs from Kac-Moody algebras, Interpolation theorem for a continuous function on orientations of a simple graph, Ribbon tilings and multidimensional height functions, Legal coloring of graphs, The asymptotic number of acyclic digraphs. I, Chip-firing game and a partial Tutte polynomial for Eulerian digraphs, On the computational complexity of the order polynomial, FPT algorithms to enumerate and count acyclic and totally cyclic orientations, Generating all the acyclic orientations of an undirected graph, Generalized Dehn-Sommerville relations for hypergraphs, Increasing spanning forests in graphs and simplicial complexes, Searching for acyclic orientations of graphs, Graphical Eulerian numbers and chromatic generating functions, Transfer-matrix methods meet Ehrhart theory, Efficient enumeration of graph orientations with sources, Chromatic polynomials and network reliability, Lattice point counts for the Shi arrangement and other affinographic hyperplane arrangements, Generalised chromatic polynomials of graphs from heaps of pieces, The number of nowhere-zero flows on graphs and signed graphs, Chromatic polynomials with least coefficients, A bibliography on chromatic polynomials, Plethysms of chromatic and Tutte symmetric functions, The domination polynomial of a graph at \(-1\), Deformations of the braid arrangement and trees, Enumerating degree sequences in digraphs and a cycle--cocycle reversing system, A chromatic partition polynomial, Counting acyclic digraphs by sources and sinks, Principal \(\Gamma\)-cone for a tree, Orientations, lattice polytopes, and group arrangements. II: Modular and integral flow polynomials of graphs, Combinatorics of diagrams of permutations, Order polynomials and Pólya's enumeration theorem., Bivariate order polynomials, Convexity in oriented matroids, Some inequalities for the Tutte polynomial, Counting extensional acyclic digraphs, Sur l'évaluation \(t(M;2,0)\) du polynôme de Tutte d'un matroide et une conjecture de B. Grünbaum rélative aux arrangements de droites du plan, Root multiplicities for Borcherds algebras and graph coloring, On the cyclically fully commutative elements of Coxeter groups., Bijections between pattern-avoiding fillings of Young diagrams, Signed graph coloring, The number of orientable small covers over cubes, Descents, quasi-symmetric functions, Robinson-Schensted for posets, and the chromatic symmetric function, Chromatic invariants of signed graphs, Tutte polynomials and related asymptotic limiting functions for recursive families of graphs, Bases, reorientations, and linear programming, in uniform and rank-3 oriented matroids, Orientations, lattice polytopes, and group arrangements I: Chromatic and tension polynomials of graphs, Set maps, umbral calculus, and the chromatic polynomial, Group pinning consensus under fixed and randomly switching topologies with acyclic partition, Orientation of signed graphs, Ehrhart theory, modular flow reciprocity, and the Tutte polynomial, On weak chromatic polynomials of mixed graphs, Maximizing proper colorings on graphs, The odd-even invariant for graphs, The active bijection for graphs, A bivariate chromatic polynomial for signed graphs, Partial graph orientations and the Tutte polynomial, On the structure of oriented graphs and digraphs with forbidden tournaments or cycles, Orientations, lattice polytopes, and group arrangements. III: Cartesian product arrangements and applications to Tutte type polynomials, Colorings and orientations of graphs, A note on a counting problem arising in percolation theory, Tutte polynomials for counting and classifying orbits, On the number of labeled acyclic digraphs, An inequality for Tutte polynomials, Maximization of the Choquet integral over a convex set and its application to resource allocation problems, The Whitney duals of a graded poset, A generalized chromatic polynomial, acyclic orientations with prescribed sources and sinks, and network reliability, Holomorphic quadratic differentials on graphs and the chromatic polynomial, The number of spanning trees of a family of 2-separable weighted graphs, The topology of the coloring complex, Binomial edge ideals and conditional independence statements, Functions of random walks on hyperplane arrangements, Degree-constrained orientation of maximum satisfaction: graph classes and parameterized complexity, A decision support system for vine growers based on a Bayesian network, Oriented gain graphs, line graphs and eigenvalues, Linear stationary control systems over the Boolean semiring and their graphs of modules, The number of small covers over cubes, Acyclic and totally cyclic orientations of combinatorial geometries, The multi-indexed partitional, Chromatic polynomials of complements of bipartite graphs, Chromatic posets, From a zoo to a zoology: Towards a general theory of graph polynomials, A bijection for Eulerian-equivalence classes of totally cyclic orientations, Affine and toric hyperplane arrangements, On the number of forests and connected spanning subgraphs, Acyclic orientations of random graphs, The homology of the cyclic coloring complex of simple graphs, Asymptotic behavior of acyclic and cyclic orientations of directed lattice graphs, Elements of a theory of simulation. II: Sequential dynamical systems., Monomial bases for broken circuit complexes, The active bijection in graphs, hyperplane arrangements, and oriented matroids, 1: the fully optimal basis of a bounded region, Elements of a theory of computer simulation. I, Combinatorial reciprocity for the chromatic polynomial and the chromatic symmetric function, The Tutte polynomial of a morphism of matroids. I: Set-pointed matroids and matroid perspectives, Sinks in acyclic orientations of graphs, The acyclic sets of an oriented matroid, Forests, colorings and acyclic orientations of the square lattice, Density via duality., The chromatic polynomial of an unlabeled graph, Burnside chromatic polynomials of group-invariant graphs, Acyclic reorientations of weakly oriented matroids, The rank and minimal border strip decompositions of a skew partition, Pruned inside-out polytopes, combinatorial reciprocity theorems and generalized permutahedra, Degree-constrained graph orientation: maximum satisfaction and minimum violation
Cites Work
