A note on recognizing an old friend in a new place: list coloring and the zero-temperature Potts model

DOI10.4171/AIHPD/12MaRDI QIDQ2019203zbMATH OpenOpenAlexFDO

Authors Joanna A. Ellis-Monaghan, Iain Moffatt

Publication date 27 March 2015

Published in Annales de l'Institut Henri Poincaré D. Combinatorics, Physics and their Interactions (AIHPD) (Search for Journal in Brave)

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

zbMATH Keywords

antiferromagneticexternal fieldgraph coloringlist coloringPotts modelstatistical mechanicszero-temperature limit

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph polynomials (05C31) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20)

Abstract: Here we observe that list coloring in graph theory coincides with the zero-temperature antiferromagnetic Potts model with an external field. We give a list coloring polynomial that equals the partition function in this case. This is analogous to the well-known connection between the chromatic polynomial and the zero-temperature, zero-field, antiferromagnetic Potts model. The subsequent cross fertilization yields immediate results for the Potts model and suggests new research directions in list coloring.

Review text

The authors find a connection between a heavily-studied area of graph theory and the zero-temperature Potts model with an external field. Firsty they provide a brief review of the \(V\)-polynomial and its specialization to the Potts model with an external field. Then they show that list coloring in graph theory coincides with the zero-temp antiferromagnetic Potts model with an external field. Moreover, a list coloring polynomial is given which equals the partition function in this case. These yields some results for the Potts model and suggests new research directions in list coloring.

Recommendations

• Potts model and graph theory.
• Exact results on Potts model partition functions in a generalized external field and weighted-set graph colorings
• A little statistical mechanics for the graph theorist
• Some exact results on the Potts model partition function in a magnetic field
• On the Potts model partition function in an external field

Cites work

• A little statistical mechanics for the graph theorist
• A weighted graph polynomial from chromatic invariants of knots
• Boundary chromatic polynomial
• Bounds on the complex zeros of (di)chromatic polynomials and Potts-model partition functions
• Chromatic Roots are Dense in the Whole Complex Plane
• Every planar graph is 5-choosable
• Exact results on Potts model partition functions in a generalized external field and weighted-set graph colorings
• Generalized coloring for tree-like graphs
• scientific article; zbMATH DE number 437298 (Why is no real title available?)
• scientific article; zbMATH DE number 3856167 (Why is no real title available?)
• scientific article; zbMATH DE number 3735847 (Why is no real title available?)
• scientific article; zbMATH DE number 3563170 (Why is no real title available?)
• scientific article; zbMATH DE number 1179517 (Why is no real title available?)
• Lattice points in orthotopes and a huge polynomial Tutte invariant of weighted gain graphs
• On the complexity of some colorful problems parameterized by treewidth
• On the Potts model partition function in an external field
• On the uniqueness of Gibbs states in the Pirogov-Sinai theory
• The multivariate Tutte polynomial (alias Potts model) for graphs and matroids
• The Potts model and the Tutte polynomial.
• The Tutte-Potts connection in the presence of an external magnetic field
• Weighted-set graph colorings

Cited in

(1)

• A vertex-weighted Tutte symmetric function, and constructing graphs with equal chromatic symmetric function

This page was built for publication: A note on recognizing an old friend in a new place: list coloring and the zero-temperature Potts model

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2019203)