The Potts model and chromatic functions of graphs
Annales de l’Institut Henri Poincaré D, Tome 1 (2014) no. 1, pp. 47-60.

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.

Publié le :
DOI : 10.4171/aihpd/2
Classification : 05-XX, 82-XX
Mots-clés : Graph polynomial, chromatic polynomial, U-polynomial, graph coloring, integer partition, Potts model
@article{AIHPD_2014__1_1_47_0,
     author = {Klazar, Martin and Loebl, Martin and Moffatt, Iain},
     title = {The {Potts} model and chromatic functions of graphs},
     journal = {Annales de l{\textquoteright}Institut Henri Poincar\'e D},
     pages = {47--60},
     volume = {1},
     number = {1},
     year = {2014},
     doi = {10.4171/aihpd/2},
     mrnumber = {3166202},
     zbl = {1285.05094},
     language = {en},
     url = {http://archive.numdam.org/articles/10.4171/aihpd/2/}
}
TY  - JOUR
AU  - Klazar, Martin
AU  - Loebl, Martin
AU  - Moffatt, Iain
TI  - The Potts model and chromatic functions of graphs
JO  - Annales de l’Institut Henri Poincaré D
PY  - 2014
SP  - 47
EP  - 60
VL  - 1
IS  - 1
UR  - http://archive.numdam.org/articles/10.4171/aihpd/2/
DO  - 10.4171/aihpd/2
LA  - en
ID  - AIHPD_2014__1_1_47_0
ER  - 
%0 Journal Article
%A Klazar, Martin
%A Loebl, Martin
%A Moffatt, Iain
%T The Potts model and chromatic functions of graphs
%J Annales de l’Institut Henri Poincaré D
%D 2014
%P 47-60
%V 1
%N 1
%U http://archive.numdam.org/articles/10.4171/aihpd/2/
%R 10.4171/aihpd/2
%G en
%F AIHPD_2014__1_1_47_0
Klazar, Martin; Loebl, Martin; Moffatt, Iain. The Potts model and chromatic functions of graphs. Annales de l’Institut Henri Poincaré D, Tome 1 (2014) no. 1, pp. 47-60. doi : 10.4171/aihpd/2. http://archive.numdam.org/articles/10.4171/aihpd/2/

Cité par Sources :