Chromatic Polynomials for Families of Strip Graphs and their Asymptotic Limits

preprint1997arXivOpen access

Abstract

We calculate the chromatic polynomials P((Gs)m,q)P((G_s)_m,q) and, from these, the asymptotic limiting functions W({Gs},q)=lim⁡n→∞P(Gs,q)1/nW(\{G_s\},q)=\lim_{n \to \infty}P(G_s,q)^{1/n} for families of nn-vertex graphs (Gs)m(G_s)_m comprised of mm repeated subgraphs HH adjoined to an initial graph II. These calculations of W({Gs},q)W(\{G_s\},q) for infinitely long strips of varying widths yield important insights into properties of W(Λ,q)W(Λ,q) for two-dimensional lattices ΛΛ. In turn, these results connect with statistical mechanics, since W(Λ,q)W(Λ,q) is the ground state degeneracy of the qq-state Potts model on the lattice ΛΛ. 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({Gs},q)W(\{G_s\},q) function in the limit n→∞n \to \infty. From this, we obtain the exact continuous locus of points B{\cal B} where W({Gs},q)W(\{G_s\},q) is nonanalytic in the complex qq plane. This locus is shown to consist of arcs which do not separate the qq plane into disconnected regions. Zeros of chromatic polynomials are computed for finite strips and compared with the exact locus of singularities B{\cal B}. We find that as the width of the infinitely long strips is increased, the arcs comprising B{\cal B} elongate and move toward each other, which enables one to understand the origin of closed regions that result for the (infinite) 2D lattice.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.