JournalsaihpdVol. 1, No. 4pp. 429–442

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

  • Joanna A. Ellis-Monaghan

    Saint Michael's College, Colchester, USA
  • Iain Moffatt

    Royal Holloway, University of London, Egham, UK
A note on recognizing an old friend in a new place: list coloring and the zero-temperature Potts model cover
Download PDF

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

Cite this article

Joanna A. Ellis-Monaghan, Iain Moffatt, 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), no. 4, pp. 429–442

DOI 10.4171/AIHPD/12