1996/12/31 by Robert Shrock, Shan-Ho Tsai
Mathematics · Physics and Astronomy · #Antiferromagnetism #Chromatic polynomial #Chromatic scale #Combinatorics #Discrete mathematics #Graph theory and applications #Mathematics #Phase transition #Physics #Potts model #Quantum mechanics #Stochastic processes and statistical mechanics #Theoretical and Computational Physics #cond-mat.stat-mech #hep-lat #math.CO
paper · pdf · doi:10.1103/physreve.55.5165
published as Phys. Rev. E55, 5165 (1997) · 33 pages, Latex, 5 postscript figures, published version; includes further comments on large-q series
arxiv created 1997/04/03 · openalex publication_date 1997/05/01 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
We study the asymptotic limiting function W(G, q) = limn→ ∞ P(G, q) 1/n, where P(G, q) is the chromatic polynomial for a graph G with n vertices. We first discuss a subtlety in the definition of W(G, q) resulting from the fact that at certain special points qs, the following limits do not commute: limn→ ∞ limq→qs P(G, q) 1/n ̸ = limq→qs limn→ ∞ P(G, q) 1/n. We then present exact calculations of W(G, q) and determine the corresponding analytic structure in the complex q plane for a number of families of graphs G, including circuits, wheels, biwheels, bipyramids, and (cyclic and twisted) ladders. We study the zeros of the corresponding chromatic polynomials and prove a theorem that for certain families of graphs, all but a finite number of the zeros lie exactly on a unit circle, whose position depends on the family. Using the connection of P(G, q) with the zero-temperature Potts antiferromagnet, we derive a theorem concerning the maximal finite real point of non-analyticity in W(G, q), denoted qc and apply this theorem to deduce that qc(sq) = 3 and qc(hc) = (3 + √ 5)/2 for the square and honeycomb lattices. Finally, numerical calculations of W(hc, q) and W(sq, q) are presented and compared with series expansions and bounds.