A tree-decomposed transfer matrix for computing exact Potts model partition functions for arbitrary graphs, with applications to planar graph colourings

DOI10.1088/1751-8113/43/38/385001zbMath1200.82004arXiv1003.4847OpenAlexW2132420400WikidataQ58082275 ScholiaQ58082275MaRDI QIDQ3161084

Andrea Bedini, Jesper Lykke Jacobsen

Publication date: 11 October 2010

Published in: Journal of Physics A: Mathematical and Theoretical (Search for Journal in Brave)

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

zbMATH Keywords

transfer matrixrandom graphsPotts modelvertex colourings

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20) Coloring of graphs and hypergraphs (05C15)

Related Items (5)

tutte ⋮ Parallel family trees for transfer matrices in the Potts model ⋮ Is the five-flow conjecture almost false? ⋮ The three-state Potts antiferromagnet on plane quadrangulations ⋮ A generalized Beraha conjecture for non-planar graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Graph minors. III. Planar tree-width
• Zeroes of chromatic polynomials: A new approach to Beraha conjecture using quantum groups
• Planar triangulations with real chromatic roots arbitrarily close to 4
• Treewidth computations. I: Upper bounds
• A partial k-arboretum of graphs with bounded treewidth
• Transfer matrices and partition-function zeros for antiferromagnetic Potts models. III: Triangular-lattice chromatic polynomial
• Phase diagram of the chromatic polynomial on a torus
• Transfer matrices and partition-function zeros for antiferromagnetic Potts models. IV. Chromatic polynomial with cyclic boundary conditions
• Coloring Random Graphs
• Chromatic polynomials of large triangular lattices
• Uniform random sampling of planar graphs in linear time
• New upper bounds on the decomposability of planar graphs
• Bulk, surface and corner free-energy series for the chromatic polynomial on the square and triangular lattices
• A Separator Theorem for Nonplanar Graphs
• Every planar map is four colorable
• Evaluating the Tutte Polynomial for Graphs of Bounded Tree-Width
• A Zero-Free Interval for Chromatic Polynomials of Graphs
• The Zero-Free Intervals for Chromatic Polynomials of Graphs
• On the computational complexity of the Jones and Tutte polynomials
• Chromatic Roots are Dense in the Whole Complex Plane
• A Contribution to the Theory of Chromatic Polynomials
• Chromatic Polynomials
• Transfer matrices and partition-function zeros for antiferromagnetic Potts models. I: General theory and square-lattice chromatic polynomial.
• Transfer matrices and partition-function zeros for antiferromagnetic Potts models. II: Extended results for square-lattice chromatic polynomial.

This page was built for publication: A tree-decomposed transfer matrix for computing exact Potts model partition functions for arbitrary graphs, with applications to planar graph colourings