Anti-ferromagnetic Potts model and chromatic number I do some research on $q$-state anti-ferromagnetic Potts model in relation with graph coloring. I found that if $q$ is bigger than the chromatic number of the underling graph then there is a one-to-one correspondence between ground state of the model and proper $q$-coloring of the graph.
Is it possible that $q$ is less than the chromatic number ?
 A: Given a graph $G=(V,E)$ on $N$ vertices and $M$ edges, a (proper) $q$ coloring of $G$ is an assignment of values from $\{1,\ldots ,q\}$ to the vertices such that no two vertices connected by an edge share the same value. $G$ is $q$-colorable
if there is a proper coloring of $G$ using $q$ or fewer colors. The lowest such number is the chromatic number $q_c$. 
The chromatic polynomial $P(G,q)$ counts the number of proper $q$-colorings of
$G$, thus stating in how many ways we can color $G$ with at most $q$ colors.
One representation is in terms of spin variables $\sigma_i$ that can take values between $1$ and $q$ such that
$$P(G,q) = \sum_{\sigma_{N}=1}^{q} \cdots \sum_{\sigma_{1}=1}^{q} \, \prod_{(i,j) \in E} (1-\delta_{\sigma_{i}\sigma_{j}}) $$
Here $\delta_{x,y}$ is the Kronecker delta, with $\delta_{x,y}=1$ if and only if $x=y$.
The connection to statistical physics arises from the fact that the
chromatic polynomial equals the antiferromagnetic Potts partition
function $Z(G,q,T)$ in the zero temperature $T\rightarrow 0$ limit. Here $Z(G,q,0)$ counts the number of possible spin configurations where all neighboring spins disalign, i.e. are unequal.
The total energy in the global state of all spins specified is given by the Hamiltonian
$$
H(\sigma) = -J \sum_{(i,j)\in E} \delta_{\sigma_{i}\sigma_{j}}
$$
where $\sigma=(\sigma_1,\ldots,\sigma_N)$ is the full system state and $J$ is the interaction strength. The partition function for this system
at positive temperature $T = (k_{B}\beta)^{-1}$ is
$$
Z(G,q,T) = \sum_{\sigma}e^{-\beta H(\sigma)} = \sum_{\sigma} \prod_{(i,j) \in E} (1 + (e^{\beta J} - 1) \delta_{\sigma_{i}\sigma_{j}})
$$
where $k_{B}$ is the Boltzmann constant. If $J<0$ (antiferromagnet)
the $T \rightarrow 0$ limit $e^{\beta J} \rightarrow 0$ yields a partition
function thus counting the number of states the system exhibits where all pairwise interaction energies (across each edge) have minimum energy, i.e. edges have disaligned spins at their ends, 
$$
\lim_{T\rightarrow 0} Z(G,q,T) = P(G,q).
$$
This relation holds for all $q$. Thus, independent of whether $q$ is larger, smaller or equal to the chromatic number, there is the one-to-one correspondence  asked for: the number of ground states of the (antiferromagnetic) Potts model equals the number of proper $q$-colorings of the underlying graph. For $q\geq q_c$, that number is positive and typically large, increasing exponentially with  the number of vertices. For $q<q_c$ there is no ground state in the sense that not all pairwise interaction energies can be simultaneously minimized. The system is called frustrated and the number of such ground states is zero, just as the number of proper $q$-colorings.
