Annales de l’Institut Henri Poincaré D


Full-Text PDF (170 KB) | Metadata | Table of Contents | AIHPD summary
Volume 1, Issue 4, 2014, pp. 429–442
DOI: 10.4171/AIHPD/12

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

Joanna A. Ellis-Monaghan[1] and Iain Moffatt[2]

(1) Department of Mathematics, Saint Michael's College, Winooski Park, VT 05439, Colchester, USA
(2) Department of Mathematics, Royal Holloway, University of London, TW20 0EX, Egham, UK

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 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.

Keywords: Potts model, external field, list coloring, graph coloring, antiferromagnetic, zero-temperature limit, statistical mechanics

Ellis-Monaghan Joanna, Moffatt Iain: A note on recognizing an old friend in a new place: list coloring and the zero-temperature Potts model. Ann. Inst. Henri Poincaré Comb. Phys. Interact. 1 (2014), 429-442. doi: 10.4171/AIHPD/12