Families of graphs with chromatic zeros lying on circles
Robert E. Shrock, Shan-Ho Tsai · Physical review. E, Statistical physics, plasmas, fluids, and related interdisciplinary topics · 1997
We define an infinite set of families of graphs, which we call $p$-wheels and denote ${(\mathrm{Wh})}_{n}^{(p)}$, that generalize the wheel $(p=1)$ and biwheel $(p=2)$ graphs. The chromatic polynomial for ${(\mathrm{Wh})}_{n}^{(p)}$ is calculated, and remarkably simple properties of the chromatic zeros are found: (i) the real zeros occur at $q=0,1,\dots{},p+1$ for $n\ensuremath{-}p$ even and $q=0,1,\dots{},p+2$ for $n\ensuremath{-}p$ odd; and (ii) the complex zeros all lie, equally spaced, on the unit circle $|q\ensuremath{-}(p+1)|=1$ in the complex $q$ plane. In the $n\ensuremath{\rightarrow}\ensuremath{\infty}$ limit, the zeros on this circle merge to form a boundary curve separating two regions where the limiting function $W({{(\mathrm{Wh})}^{(p)}},q)$ is analytic, viz., the exterior and interior of the above circle. Connections with statistical mechanics are noted.