CHROMATIC POLYNOMIALS FOR FAMILIES OF STRIP GRAPHS AND THEIR ASYMPTOTIC LIMITS

We calculate the chromatic polynomials P((G(s))(m),q) and, from these, the asymptotic limiting functions W({G(s)},q)= lim(n-->infinity) P(G( s),q)(1/n) for families of n-vertex graphs (G(s))(m) comprised of In r epeated subgraphs H adjoined to an initial graph I. These calculations of TP({G(s)},q) for infinitely long strips of varying widths yield im portant insights into properties of W(Lambda, q) for two-dimensional l attices Lambda. In turn, these results connect with statistical mechan ics, since W(Lambda,q) is the ground-state degeneracy of the q-state P otts 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-->infinity. From this, we obtain the exact continuous locus of points R 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 exac t locus of singularities R. We find that as the width of the infinitel y long strips is increased, the arcs comprising R elongate and move to ward each other, which enables one to understand the origin of closed regions that result for the (infinite) 2D lattice. (C) 1998 Elsevier S cience B.V. All rights reserved.