The Structure of Chromatic Polynomials of Planar Triangulation Graphs and Implications for Chromatic Zeros and Asymptotic Limiting Quantities

We present an analysis of the structure and properties of chromatic polynomials $P(G_{pt,\vec m},q)$ of one-parameter and multi-parameter families of planar triangulation graphs $G_{pt,\vec m}$, where ${\vec m} = (m_1,...,m_p)$ is a vector of integer parameters. We use these to study the ratio of $|P(G_{pt,\vec m},τ+1)|$ to the Tutte upper bound $(τ-1)^{n-5}$, where $τ=(1+\sqrt{5} \ )/2$ and $n$ is the number of vertices in $G_{pt,\vec m}$. In particular, we calculate limiting values of this ratio as $n \to \infty$ for various families of planar triangulations. We also use our calculations to study zeros of these chromatic polynomials. We study a large class of families $G_{pt,\vec m}$ with $p=1$ and $p=2$ and show that these have a structure of the form $P(G_{pt,m},q) = c_{_{G_{pt}},1}λ_1^m + c_{_{G_{pt}},2}λ_2^m + c_{_{G_{pt}},3}λ_3^m$ for $p=1$, where $λ_1=q-2$, $λ_2=q-3$, and $λ_3=-1$, and $P(G_{pt,\vec m},q) = \sum_{i_1=1}^3 \sum_{i_2=1}^3 c_{_{G_{pt}},i_1 i_2} λ_{i_1}^{m_1}λ_{i_2}^{m_2}$ for $p=2$. We derive properties of the coefficients $c_{_{G_{pt}},\vec i}$ and show that $P(G_{pt,\vec m},q)$ has a real chromatic zero that approaches $(1/2)(3+\sqrt{5} \ )$ as one or more of the $m_i \to \infty$. The generalization to $p \ge 3$ is given. Further, we present a one-parameter family of planar triangulations with real zeros that approach 3 from below as $m \to \infty$. Implications for the ground-state entropy of the Potts antiferromagnet are discussed.

No reviews yet.

No comments yet.