Geodesic
Counting proper colourings in 4-regular graphs via the Potts model
Ewan Davies1
1Universiteit van Amsterdam
The electronic journal of combinatorics, Tome 25 (2018) no. 4
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

We give tight upper and lower bounds on the internal energy per particle in the antiferromagnetic $q$-state Potts model on $4$-regular graphs, for $q\ge 5$. This proves the first case of a conjecture of the author, Perkins, Jenssen and Roberts, and implies tight bounds on the antiferromagnetic Potts partition function. The zero-temperature limit gives upper and lower bounds on the number of proper $q$-colourings of $4$-regular graphs, which almost proves the case $d=4$ of a conjecture of Galvin and Tetali. For any $q \ge 5$ we prove that the number of proper $q$-colourings of a $4$-regular graph is maximised by a union of $K_{4,4}$'s.
DOI : 10.37236/7743
Classification : 05C15, 82B20, 90C35
Mots-clés : graph colouring, Potts model, graph homomorphisms

Ewan Davies  1

1 Universiteit van Amsterdam 
@article{10_37236_7743,
     author = {Ewan Davies},
     title = {Counting proper colourings in 4-regular graphs via the {Potts} model},
     journal = {The electronic journal of combinatorics},
     year = {2018},
     volume = {25},
     number = {4},
     doi = {10.37236/7743},
     zbl = {1398.05082},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/7743/}
}
TY  - JOUR
AU  - Ewan Davies
TI  - Counting proper colourings in 4-regular graphs via the Potts model
JO  - The electronic journal of combinatorics
PY  - 2018
VL  - 25
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.37236/7743/
DO  - 10.37236/7743
ID  - 10_37236_7743
ER  - 
%0 Journal Article
%A Ewan Davies
%T Counting proper colourings in 4-regular graphs via the Potts model
%J The electronic journal of combinatorics
%D 2018
%V 25
%N 4
%U http://geodesic.mathdoc.fr/articles/10.37236/7743/
%R 10.37236/7743
%F 10_37236_7743
Ewan Davies. Counting proper colourings in 4-regular graphs via the Potts model. The electronic journal of combinatorics, Tome 25 (2018) no. 4. doi: 10.37236/7743

Cité par Sources :