Annales de l’Institut Henri Poincaré D


Full-Text PDF (154 KB) | Metadata | Table of Contents | AIHPD summary
Volume 1, Issue 1, 2014, pp. 47–60
DOI: 10.4171/AIHPD/2

The Potts model and chromatic functions of graphs

Martin Klazar[1], Martin Loebl[2] and Iain Moffatt[3]

(1) Department of Applied Mathematics (KAM & ITI), Charles University, Malostranske nam. 25, 118 00, Prague 1, Czechia
(2) Department of Applied Mathematics (KAM & ITI), Charles University, Malostranske nam. 25, 118 00, Prague 1, Czechia
(3) Department of Mathematics, Royal Holloway, University of London, TW20 0EX, Egham, UK

The $U$-polynomial of Noble and Welsh is known to have intimate connections with the Potts model as well as with several important graph polynomials. For each graph $G$, $U(G)$ is equivalent to the Stanley's symmetric bad colouring polynomial $XB(G)$. Moreover Sarmiento established the equivalence between $U$ and the polychromate of Brylawski. All these functions have countable number of variables, even though the restrictions to an arbitrary graph are honest polynomials. Loebl defined the $q$-dichromate $B_q(G,x,y)$ as a function of graph $G$ and three independent variables $q,x,y$, proved that it is equal to the partition function of the Potts model with variable number of states and with certain magnetic field contribution, and conjectured that $q$-dichromate is equivalent to the $U$-polynomial. He also proposed a stronger conjecture on integer partitions. The aim of this paper is two-fold. We present a construction disproving the Loebl's integer partitions conjecture, and we introduce a new function $B_{r,q}(G,x,k)$ which is also equal to the partition function of the Potts model with variable number of states and with a (different) external field contribution, and we show that $B_{r,q}(G,x,k)$ is equivalent to $U$-polynomial. This gives a Potts model-type formulation for the $U$-polynomial.

Keywords: Graph polynomial, chromatic polynomial, U-polynomial, graph coloring, integer partition, Potts model

Klazar Martin, Loebl Martin, Moffatt Iain: The Potts model and chromatic functions of graphs. Ann. Inst. Henri Poincaré Comb. Phys. Interact. 1 (2014), 47-60. doi: 10.4171/AIHPD/2