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

Abstract

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}},\tau +1)|$ to the Tutte upper bound $(\tau -1{)}^{n-5}$, where $\tau =(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}{\lambda }_1^m+c_{{}_{G_{pt}},2}{\lambda }_2^m+c_{{}_{G_{pt}},3}{\lambda }_3^m$ for $p=1$, where ${\lambda }_1=q-2$, ${\lambda }_2=q-3$, and ${\lambda }_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}{\lambda }_{i_1}^{m_1}{\lambda }_{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.

57 pages, latex, 15 figures

References in corpus (4)

• Kuramoto model of synchronization: Equilibrium and nonequilibrium aspects
• Potts Model Partition Functions for Self-Dual Families of Strip Graphs
• Exact Potts/Tutte Polynomials for Polygon Chain Graphs
• Chromatic polynomials of random graphs

Cited by in corpus (1)

• Potts Partition Function Zeros and Ground State Entropy on Hanoi Graphs