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

Published online: 2014-12-31

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) Saint Michael's College, Colchester, USA
(2) Royal Holloway, University of London, 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