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 -