TY - JOUR
T1 - On the chromatic roots of generalized theta graphs
AU - Brown, Jason I.
AU - Hickman, Carl
AU - Sokal, Alan D.
AU - Wagner, David G.
N1 - Funding Information:
We thank Karl Dilcher for many helpful conversations concerning the roots of trinomials, and for sharing with us his unpublished notes [12]. One of us (A.D.S.) also thanks Rob Corless and David Jeffrey for extremely helpful correspondence concerning the Lambert W function; in particular, Rob’s computation of the first few terms of a series closely related to (5.13) was an essential stimulus for our realizing that such expansions might be convergent. This research was supported in part by NSF Grant PHY-9900769 (A.D.S.) and operating grants from NSERC (J.B., C.H., and D.G.W.). It was completed while one of the authors (A.D.S.) was a Vis iting Fellow at All Souls College, Oxford, where his work was s upported in part by EPSRC Grant GR/M 71626 and aided by the warm hospitality of John Cardy and the Department of Theoretical Physics.
PY - 2001
Y1 - 2001
N2 - The generalized theta graph χS1,⋯,Sk consists of a pair of endvertices joined by k internally disjoint paths of lengths S1,⋯,Sk≥1. We prove that the roots of the chromatic polynomial π(χS1,⋯,Sk, Z) of a k-ary generalized theta graph all lie in the disc z - 1 ≤ [ 1 + o (1) ]k/log k, uniformly in the path lengths Si. Moreover, we prove that χ2,⋯,2≃K2 indeed has a chromatic root of modulus [1+0(1)]k/log k. Finally, for k ≤ 8 we prove that the generalized theta graph with a chromatic root that maximizes z - 1 is the one with all path lengths equal to 2; we conjecture that this holds for all k.
AB - The generalized theta graph χS1,⋯,Sk consists of a pair of endvertices joined by k internally disjoint paths of lengths S1,⋯,Sk≥1. We prove that the roots of the chromatic polynomial π(χS1,⋯,Sk, Z) of a k-ary generalized theta graph all lie in the disc z - 1 ≤ [ 1 + o (1) ]k/log k, uniformly in the path lengths Si. Moreover, we prove that χ2,⋯,2≃K2 indeed has a chromatic root of modulus [1+0(1)]k/log k. Finally, for k ≤ 8 we prove that the generalized theta graph with a chromatic root that maximizes z - 1 is the one with all path lengths equal to 2; we conjecture that this holds for all k.
KW - Chromatic polynomial
KW - Chromatic roots
KW - Complete bipartite graph
KW - Generalized theta graph
KW - Graph
KW - Lambert W function
KW - Potts model
KW - Series-parallel graph
UR - http://www.scopus.com/inward/record.url?scp=0035200481&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=0035200481&partnerID=8YFLogxK
U2 - 10.1006/jctb.2001.2057
DO - 10.1006/jctb.2001.2057
M3 - Article
AN - SCOPUS:0035200481
SN - 0095-8956
VL - 83
SP - 272
EP - 297
JO - Journal of Combinatorial Theory. Series B
JF - Journal of Combinatorial Theory. Series B
IS - 2
ER -