Exact Chromatic Polynomials for Toroidal Chains of Complete Graphs

Abstract

We present exact calculations of the partition function of the zero-temperature Potts antiferromagnet (equivalently, the chromatic polynomial) for graphs of arbitrarily great length composed of repeated complete subgraphs $K_b$ with $b=5,6$ which have periodic or twisted periodic boundary condition in the longitudinal direction. In the $L_x\to \infty$ limit, the continuous accumulation set of the chromatic zeros $\mathcal{B}$ is determined. We give some results for arbitrary $b$ including the extrema of the eigenvalues with coefficients of degree $b-1$ and the explicit forms of some classes of eigenvalues. We prove that the maximal point where $\mathcal{B}$ crosses the real axis, $q_c$, satisfies the inequality $q_c\le b$ for $2\le b$, the minimum value of $q$ at which $\mathcal{B}$ crosses the real $q$ axis is $q=0$, and we make a conjecture concerning the structure of the chromatic polynomial for Klein bottle strips.

36 pages, latex, 2 postscript figures included

References in corpus (5)

• Exact Potts Model Partition Functions on Wider Arbitrary-Length Strips of the Square Lattice
• Exact Potts Model Partition Function for Strips of the Square Lattice
• Complex-Temperature Phase Diagrams for the q-State Potts Model on Self-Dual Families of Graphs and the Nature of the $q\to \infty$ Limit
• Potts Model Partition Functions for Self-Dual Families of Strip Graphs
• Exact T=0 Partition Functions for Potts Antiferromagnets on Sections of the Simple Cubic Lattice