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.

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