# Chromatic Polynomials for Families of Strip Graphs and their Asymptotic
Limits

Research paper by **Martin Rocek, Robert Shrock, Shan-Ho Tsai**

Indexed on: **13 Dec '97**Published on: **13 Dec '97**Published in: **Physics - Statistical Mechanics**

Join Sparrho today to stay on top of science

Discover, organise and share research that matters to you

Join Sparrho today to stay on top of science

Discover, organise and share research that matters to you

Join for free

#### 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 ${\cal 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 ${\cal B}$. We find that as the width of the
infinitely long strips is increased, the arcs comprising ${\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.