TY  - JOUR
A1  - Royle, GF
A1  - Sokal, AD
JF  - SIAM Journal on Discrete Mathematics
UR  - http://dx.doi.org/10.1137/130930133
SN  - 0895-4801
IS  - 4
N1  - © 2015, Society for Industrial and Applied Mathematics.
SP  - 2117
VL  - 29
KW  - Applied
KW  -  Mathematics
KW  -  chromatic polynomial
KW  -  multivariate Tutte polynomial
KW  -  antiferromagnetic Potts model
KW  -  chromatic roots
KW  -  maxmaxflow
KW  -  series-parallel graph
KW  -  MODEL PARTITION-FUNCTIONS
KW  -  NONCOMPACT W BOUNDARIES
KW  -  GROUND-STATE DEGENERACY
KW  -  RELIABILITY POLYNOMIALS
KW  -  POTTS ANTIFERROMAGNETS
KW  -  COMPLEX ZEROS
KW  -  ALGORITHMS
KW  -  SUBGRAPHS
KW  -  REGIONS
KW  -  chromatic polynomial
KW  -  multivariate Tutte polynomial
KW  -  antiferromagnetic Potts
model
KW  -  chromatic roots
KW  -  maxmaxflow
KW  -  series-parallel graph
PB  - SIAM PUBLICATIONS
N2  - We prove that the (real or complex) chromatic roots of a series-parallel graph with maxmaxflow $\Lambda$ lie in the disc $|q-1| < (\Lambda-1)/\log 2$. More generally, the same bound holds for the (real or complex) roots of the multivariate Tutte polynomial when the edge weights lie in the ?real antiferromagnetic regime? $-1 \le v_e \le 0$. For each $\Lambda \geq 3$, we exhibit a family of graphs, namely, the ?leaf-joined trees?, with maxmaxflow $\Lambda$ and chromatic roots accumulating densely on the circle $|q-1|=\Lambda -1$, thereby showing that our result is within a factor $1/\log 2 \approx 1.442695$ of being sharp.
ID  - discovery1399078
AV  - public
Y1  - 2015/01/01/
EP  - 2159
TI  - Linear Bound in Terms of Maxmaxflow for the Chromatic Roots of Series-Parallel Graphs
ER  -