Chromatic Polynomials for Families of Strip Graphs and their Asymptotic Limits

Abstract

We calculate the chromatic polynomials $P((G_s{)}_m,q)$ and, from these, the asymptotic limiting functions $W(\{G_s\},q)={\lim }_{n\to \infty }P(G_s,q{)}^{1/n}$ for families of $n$-vertex graphs $(G_s{)}_m$ comprised of $m$ repeated subgraphs $H$ adjoined to an initial graph $I$. These calculations of $W(\{G_s\},q)$ for infinitely long strips of varying widths yield important insights into properties of $W(\Lambda ,q)$ for two-dimensional lattices $\Lambda$. In turn, these results connect with statistical mechanics, since $W(\Lambda ,q)$ is the ground state degeneracy of the $q$-state Potts model on the lattice $\Lambda$. For our calculations, we develop and use a generating function method, which enables us to determine both the chromatic polynomials of finite strip graphs and the resultant $W(\{G_s\},q)$ function in the limit $n\to \infty$. From this, we obtain the exact continuous locus of points $\mathcal{B}$ where $W(\{G_s\},q)$ is nonanalytic in the complex $q$ plane. This locus is shown to consist of arcs which do not separate the $q$ plane into disconnected regions. Zeros of chromatic polynomials are computed for finite strips and compared with the exact locus of singularities $\mathcal{B}$. We find that as the width of the infinitely long strips is increased, the arcs comprising $\mathcal{B}$ elongate and move toward each other, which enables one to understand the origin of closed regions that result for the (infinite) 2D lattice.

48 pages, Latex, 12 encapsulated postscript figures, to appear in Physica A

References in corpus (5)

• Lower Bounds and Series for the Ground State Entropy of the Potts Antiferromagnet on Archimedean Lattices and their Duals
• Families of Graphs with W_r({G},q) Functions That Are Nonanalytic at 1/q=0
• Upper and Lower Bounds for Ground State Entropy of Antiferromagnetic Potts Models
• Ground State Entropy of Potts Antiferromagnets: Bounds, Series, and Monte Carlo Measurements
• Complex-Temperature Phase Diagrams of 1D Spin Models with Next-Nearest-Neighbor Couplings

Cited by in corpus (54)

• Chromatic roots are dense in the whole complex plane
• Transfer Matrices and Partition-Function Zeros for Antiferromagnetic Potts Models I. General Theory and Square-Lattice Chromatic Polynomial
• Exact Potts Model Partition Functions on Ladder Graphs
• Thin Fisher Zeroes
• A Little Statistical Mechanics for the Graph Theorist
• Exact Potts Model Partition Functions on Wider Arbitrary-Length Strips of the Square Lattice
• Exact Potts Model Partition Function on Strips of the Triangular Lattice
• T=0 Partition Functions for Potts Antiferromagnets on Square Lattice Strips with (Twisted) Periodic Boundary Conditions
• Chromatic Polynomials for $J(\prod H)I$ Strip Graphs and their Asymptotic Limits
• Ground State Entropy of Potts Antiferromagnets: Homeomorphic Classes with Noncompact W Boundaries
• Structural Properties of Potts Model Partition Functions and Chromatic Polynomials for Lattice Strips
• Ground State Entropy of Potts Antiferromagnets on Homeomorphic Families of Strip Graphs
• T=0 Partition Functions for Potts Antiferromagnets on Moebius Strips and Effects of Graph Topology
• Ground State Entropy of Potts Antiferromagnets: Cases with Noncompact W Boundaries Having Multiple Points at 1/q = 0
• Ground-State Degeneracy of Potts Antiferromagnets on Two-Dimensional Lattices: Approach Using Infinite Cyclic Strip Graphs
• Ground State Entropy of Potts Antiferromagnets and the Approach to the 2D Thermodynamic Limit
• Ground State Entropy of the Potts Antiferromagnet on Strips of the Square Lattice
• Transfer Matrices and Partition-Function Zeros for Antiferromagnetic Potts Models II. Extended Results for Square-Lattice Chromatic Polynomial
• Exact Potts Model Partition Functions on Strips of the Honeycomb Lattice
• Transfer Matrices and Partition-Function Zeros for Antiferromagnetic Potts Models III. Triangular-Lattice Chromatic Polynomial
• Ground State Entropy of the Potts Antiferromagnet on Cyclic Strip Graphs
• Ground State Entropy of Potts Antiferromagnets on Cyclic Polygon Chain Graphs
• 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
• $q$-Plane Zeros of the Potts Partition Function on Diamond Hierarchical Graphs
• Zeros of Jones Polynomials for Families of Knots and Links
• Potts Model Partition Functions for Self-Dual Families of Strip Graphs
• Ground State Entropy of the Potts Antiferromagnet with Next-Nearest-Neighbor Spin-Spin Couplings on Strips of the Square Lattice
• T=0 Partition Functions for Potts Antiferromagnets on Lattice Strips with Fully Periodic Boundary Conditions
• Ground State Entropy of the Potts Antiferromagnet on Triangular Lattice Strips
• Exact Partition Function for the Potts Model with Next-Nearest Neighbor Couplings on Strips of the Square Lattice
• Reliability Polynomials and their Asymptotic Limits for Families of Graphs
• Exact T=0 Partition Functions for Potts Antiferromagnets on Sections of the Simple Cubic Lattice
• General Structural Results for Potts Model Partition Functions on Lattice Strips
• Potts model on recursive lattices: some new exact results
• Chromatic Polynomials for Lattice Strips with Cyclic Boundary Conditions
• Planar triangulations with real chromatic roots arbitrarily close to four
• Transfer Matrices for the Zero-Temperature Potts Antiferromagnet on Cyclic and Mobius Lattice Strips
• Exact Chromatic Polynomials for Toroidal Chains of Complete Graphs
• Tutte polynomial of pseudofractal scale-free web
• Asymptotic Behavior of Acyclic and Cyclic Orientations of Directed Lattice Graphs
• Chromatic polynomials of random graphs
• Study of Exponential Growth Constants of Directed Heteropolygonal Archimedean Lattices
• The Structure of Chromatic Polynomials of Planar Triangulation Graphs and Implications for Chromatic Zeros and Asymptotic Limiting Quantities
• Ground State Entropy of the Potts Antiferromagnet on Homeomorphic Expansions of Kagome Lattice Strips
• Counting Complex Disordered States by Efficient Pattern Matching: Chromatic Polynomials and Potts Partition Functions
• Lower Bounds on the Ground State Entropy of the Potts Antiferromagnet on Slabs of the Simple Cubic Lattice
• End Graph Effects on Chromatic Polynomials for Strip Graphs of Lattices and their Asymptotic Limits
• Improved Lower Bounds on the Ground-State Entropy of the Antiferromagnetic Potts Model
• Potts Partition Function Zeros and Ground State Entropy on Hanoi Graphs
• Ground State Entropy in Potts Antiferromagnets and Chromatic Polynomials
• Exact Results for Average Cluster Numbers in Bond Percolation on Infinite-Length Lattice Strips
• Chromatic Zeros on the Limit $G_{\infty }^{(p,\ell )}$ of the Family $G_m^{(p,\ell )}$ of Hierarchical Graphs
• Jones Polynomials and their Zeros for a Family of Knots and Links
• Exact Potts/Tutte Polynomials for Hammock Chain Graphs