Wikipedia writes:
In statistical mechanics, the Potts model, a generalization of the Ising model, is a model of interacting spins on a crystalline lattice.
From combinatorics conferences and seminars, I know that the Potts model has something to do with the chromatic polynomial, but it's not clear to me where it arises (and for which graph it's the chromatic polynomial of).
Question: What does the chromatic polynomial have to do with the Potts model?
The relationship between the chromatic polynomial and the Potts model is a special case of the relationship between the Tutte polynomial and the random cluster model of Fortuin and Kastelyn. There's a very tiny bit about this in the wikipedia page on the Tutte polynomial, but there's a section about this in Bollobàs's "Modern Graph Theory" and plenty more articles that pop up under a google search for "Tutte statistical mechanics" including "A little statistical mechanics for the graph theorist" which I've always wanted to finish reading...
By the way, it seems there's a little bit of confusion in your question about what the Potts model "is". It doesn't quite make sense to ask "for which graph is the Potts model the chromatic polynomial". The Potts model is a probabilistic model (roughly, a measure on random vertex "colorings", i.e. assign a color (often called a spin value) to each vertex) and it may be defined on any graph, where the parameters like temperature or applied field change the measure on the set of vertex colorings of the graph, e.g. at low temperatures, colorings with the same color on neighboring vertices are preferred. As typically studied in physics, the Potts model (and other such models) are put on periodic graphs (often called "lattices" in physics), such as the square lattice graph, triangular lattice graph, etc. The chromatic and Tutte polynomials show up when you compute the "partition function" associated to the model, which is a quantity like a generating function... this paragraph is a bit rough, so I'd refer to the other references.
Let me know if you have any questions. I could talk about this stuff all day.
There are a couple of references that i think are pretty decent about this subject:
These two refs talk about the chromatic polynomial: roughly speaking, you can have the number of states in the Potts model be analogous to a certain number of colors, and the chromatic polynomial emerges from the Partition Function of the system (after a suitable change of variables).
A key concept in this game is called block variables, that is, you simply walk through your lattice looking for same-state sites and binding adjacent ones together. After performing this operation in the whole lattice, you end up with "blocks" of "same state" sites, which you just define as your "new variables" and call them "block variables".
Note that you can only do this because, in principle, you have a finite system and a finite sum defining your Partition Function: in this sense, "block variables" are nothing more than a simple re-arrangement of the sum defining the Partition Function. Then, your original Partition Function,
$$ \mathcal{Z} = \sum_{{s}} e^{-\beta\, \sum_{\langle i\, j\rangle} \delta_{s_i,\, s_j}} = \sum_{{s}} \prod_{\langle i\, j\rangle} e^{-\beta\, \delta_{s_i,\, s_j}} \; ; $$
can be re-written as,
$$ \mathcal{Z} = \sum_{{s}} \prod_{\langle i\, j\rangle} (1 + v\, \delta_{s_i,\, s_j}) \; ; $$
where $ v = e^{-\beta} - 1$; and you can derive the chromatic polynomial from this last expression.
One way to think about this problem is as follows: think you have an initial and a final state, i.e., an initial lattice configuration and a final one, where the configuration is a given "spin" ("state") distribution or, analogously, a given "color" distribution.
If you think of your "colors" as "billiard balls", you can think of the process of going from the initial to the final state as a sequence of scatterings among all sites of your lattice. This way you can build an oriented graph from the initial state descending to the final one and, in some sense, the "extremization" (minimization) of the Partition Function is a sorting algorithm to run through this graph in an "efficient" way.
Anyway, I hope this gives you a flavor of how things work.
