scientific article; zbMATH DE number 1369835

DOI<link itemprop=identifier href="https://doi.org/10.1002/(SICI)1098-2418(199910/12)15:3/4<210::AID-RSA2>3.0.CO;2-R" /><210::AID-RSA2>3.0.CO;2-R 10.1002/(SICI)1098-2418(199910/12)15:3/4<210::AID-RSA2>3.0.CO;2-RzbMath0934.05057MaRDI QIDQ4704790

Dominic J. A. Welsh

Publication date: 10 April 2000

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

complexityrandom graphsTutte polynomialcoloringevaluationslattice point enumerationchip firing games

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Random graphs (graph-theoretic aspects) (05C80) Enumeration in graph theory (05C30) Combinatorial aspects of matroids and geometric lattices (05B35) Coloring of graphs and hypergraphs (05C15)

Related Items (43)

Properties of chromatic polynomials of hypergraphs not held for chromatic polynomials of graphs ⋮ A Tutte Polynomial for Maps ⋮ Counting and sampling orientations on chordal graphs ⋮ The drop polynomial of a weighted digraph ⋮ On the number of planar Eulerian orientations ⋮ Evaluations of Tutte polynomials of regular graphs ⋮ Counting degree-constrained subgraphs and orientations ⋮ The Tutte polynomial of an infinite family of outerplanar, small-world and self-similar graphs ⋮ Extremal graphs for the Tutte polynomial ⋮ Fourientation activities and the Tutte polynomial ⋮ Fourientations and the Tutte polynomial ⋮ On maximum graphs in Tutte polynomial posets ⋮ On the number of spanning trees in random regular graphs ⋮ COMBINATORIAL PROPERTIES FOR A CLASS OF SIMPLICIAL COMPLEXES EXTENDED FROM PSEUDO-FRACTAL SCALE-FREE WEB ⋮ Unnamed Item ⋮ Models of random subtrees of a graph ⋮ On some quadratic algebras. I \(\frac{1}{2}\): Combinatorics of Dunkl and Gaudin elements, Schubert, Grothendieck, Fuss-Catalan, universal Tutte and reduced polynomials ⋮ Complexity classification of the six-vertex model ⋮ Upper bound for the number of spanning forests of regular graphs ⋮ Short proof of a theorem of Brylawski on the coefficients of the Tutte polynomial ⋮ Unnamed Item ⋮ On the algebraic complexity of some families of coloured Tutte polynomials ⋮ Rank and Bollobás-Riordan polynomials: Coefficient measures and zeros ⋮ Distribution of coefficients of rank polynomials for random sparse graphs ⋮ Cohomologies of tautological bundles of matroids ⋮ A Tutte polynomial inequality for lattice path matroids ⋮ Partial graph orientations and the Tutte polynomial ⋮ A little statistical mechanics for the graph theorist ⋮ Interpretations of the Tutte and characteristic polynomials of matroids ⋮ The Merino-Welsh conjecture is false for matroids ⋮ The expansion of a chord diagram and the Tutte polynomial ⋮ Permutation Tutte polynomial ⋮ An infinite family of 2-connected graphs that have reliability factorisations ⋮ Matroid variant of Matiyasevich formula and its application ⋮ GEOMETRIC BIJECTIONS FOR REGULAR MATROIDS, ZONOTOPES, AND EHRHART THEORY ⋮ Unnamed Item ⋮ The Number of Labeled Connected Graphs Modulo Prime Powers ⋮ A Polynomial-Time Approximation Algorithm for All-Terminal Network Reliability ⋮ Interpretations for the Tutte polynomials of morphisms of matroids ⋮ Proving identities on weight polynomials of tiered trees via Tutte polynomials ⋮ Covers, orientations and factors ⋮ Combinatorial properties of Farey graphs ⋮ Determination of the bases of a splitting matroid

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Chip-firing games on graphs
• Random generation of combinatorial structures from a uniform distribution
• A spanning tree expansion of the Jones polynomial
• Approximate counting, uniform generation and rapidly mixing Markov chains
• Nowhere-zero 6-flows
• The polytope of win vectors
• Chip firing and the Tutte polynomial
• The statistics of dimers on a lattice
• Approximating the Permanent
• On the Principal Edge Tripartition of a Graph
• Decompositions of Rational Convex Polytopes
• Random walks in a convex body and an improved volume algorithm
• The Computational Complexity of the Tutte Plane: the Bipartite Case
• Randomised Approximation in the Tutte Plane
• A Randomised Approximation Algorithm for Counting the Number of Forests in Dense Graphs
• On the computational complexity of the Jones and Tutte polynomials
• Polynomial time randomized approximation schemes for Tutte–Gröthendieck invariants: The dense case
• Sur un probl?me de g?om?trie diophantienne lin?aire. I. Poly?dres et r?seaux.
• Correction: A Mixed Doubles Tournament Problem

This page was built for publication: