Forests, colorings and acyclic orientations of the square lattice

DOI10.1007/BF01608795zbMath0936.05043MaRDI QIDQ1306612

V. Pereyra

Publication date: 22 May 2000

Published in: Annals of Combinatorics (Search for Journal in Brave)

zbMATH Keywords

chromatic polynomialTutte polynomialsquare latticeacyclic orientationsforests\(k\)-colourings

Mathematics Subject Classification ID

Trees (05C05) Coloring of graphs and hypergraphs (05C15)

Related Items (21)

Tutte polynomials for benzenoid systems with one branched hexagon ⋮ The Merino-Welsh conjecture holds for series-parallel graphs ⋮ Tilings of rectangles with T-tetrominoes ⋮ The Merino-Welsh conjecture for split matroids ⋮ On the number of spanning trees in random regular graphs ⋮ On some Tutte polynomial sequences in the square lattice ⋮ Some inequalities for the Tutte polynomial ⋮ The spectrum and spanning trees of polyominos on the torus ⋮ Tutte polynomials and related asymptotic limiting functions for recursive families of graphs ⋮ Asymptotic behavior of spanning forests and connected spanning subgraphs on two-dimensional lattices ⋮ The Potts model and the Tutte polynomial ⋮ An inequality for Tutte polynomials ⋮ The number of spanning trees of a family of 2-separable weighted graphs ⋮ Potts model partition functions on two families of fractal lattices ⋮ On the number of forests and connected spanning subgraphs ⋮ Asymptotic behavior of acyclic and cyclic orientations of directed lattice graphs ⋮ Study of exponential growth constants of directed heteropolygonal Archimedean lattices ⋮ Exponential growth constants for spanning forests on Archimedean lattices: Values and comparisons of upper bounds ⋮ A note on some inequalities for the Tutte polynomial of a matroid ⋮ Spanning forests and the \(q\)-state Potts model in the limit \(q \to 0\) ⋮ The average number of spanning trees in sparse graphs with given degrees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The limit of chromatic polynomials
• Absence of phase transition for antiferromagnetic Potts models via the Dobrushin uniqueness theorem
• Lê numbers of arrangements and matroid identities
• An algorithm for the Tutte polynomials of graphs of bounded treewidth
• Approximations for chromatic polynomials
• A new subgraph expansion for obtaining coloring polynomials for graphs
• Acyclic orientations of graphs
• Bounds on the chromatic polynomial and on the number of acyclic orientations of a graph
• Generalized planar matching
• The NP-completeness column: an ongoing guide
• Graph minors. II. Algorithmic aspects of tree-width
• Colouring Square Lattice Graphs
• MULTIDIMENSIONAL LATTICES AND THEIR PARTITION FUNCTIONS
• The Rectilinear Steiner Tree Problem is $NP$-Complete
• The Rank Polynomials of Large Random Lattices
• Evaluating the Tutte Polynomial for Graphs of Bounded Tree-Width
• The Computational Complexity of the Tutte Plane: the Bipartite Case
• A Randomised Approximation Algorithm for Counting the Number of Forests in Dense Graphs
• On the computational complexity of the Jones and Tutte polynomials
• Hamilton Paths in Grid Graphs
• Polynomial time randomized approximation schemes for Tutte–Gröthendieck invariants: The dense case
• A very simple algorithm for estimating the number of k‐colorings of a low‐degree graph
• Series expansions for the q-colour problem on the square and cubic lattices
• Exact sampling with coupled Markov chains and applications to statistical mechanics

This page was built for publication: Forests, colorings and acyclic orientations of the square lattice