The EMS Publishing House is now EMS Press and has its new home at ems.press.

Please find all EMS Press journals and articles on the new platform.

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