eprintid: 1399078
rev_number: 34
eprint_status: archive
userid: 608
dir: disk0/01/39/90/78
datestamp: 2013-07-10 18:34:41
lastmod: 2021-11-29 00:45:00
status_changed: 2017-02-27 14:19:35
type: article
metadata_visibility: show
item_issues_count: 0
creators_name: Royle, GF
creators_name: Sokal, AD
title: Linear Bound in Terms of Maxmaxflow for the Chromatic Roots of Series-Parallel Graphs
ispublished: pub
divisions: UCL
divisions: B04
divisions: C06
divisions: F59
keywords: Applied, Mathematics, chromatic polynomial, multivariate Tutte polynomial, antiferromagnetic Potts model, chromatic roots, maxmaxflow, series-parallel graph, MODEL PARTITION-FUNCTIONS, NONCOMPACT W BOUNDARIES, GROUND-STATE DEGENERACY, RELIABILITY POLYNOMIALS, POTTS ANTIFERROMAGNETS, COMPLEX ZEROS, ALGORITHMS, SUBGRAPHS, REGIONS, chromatic polynomial, multivariate Tutte polynomial, antiferromagnetic Potts
model, chromatic roots, maxmaxflow, series-parallel graph
note: © 2015, Society for Industrial and Applied Mathematics.
abstract: 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.
date: 2015-01-01
publisher: SIAM PUBLICATIONS
official_url: http://dx.doi.org/10.1137/130930133
vfaculties: VMPS
oa_status: green
full_text_type: pub
language: eng
primo: open
primo_central: open_green
article_type_text: Article
verified: verified_manual
elements_source: arXiv
elements_id: 884150
doi: 10.1137/130930133
lyricists_name: Sokal, Alan
lyricists_id: ADSOK62
full_text_status: public
publication: SIAM Journal on Discrete Mathematics
volume: 29
number: 4
pagerange: 2117-2159
pages: 43
issn: 0895-4801
citation:        Royle, GF;    Sokal, AD;      (2015)    Linear Bound in Terms of Maxmaxflow for the Chromatic Roots of Series-Parallel Graphs.                   SIAM Journal on Discrete Mathematics , 29  (4)   pp. 2117-2159.    10.1137/130930133 <https://doi.org/10.1137/130930133>.       Green open access   
 
document_url: https://discovery.ucl.ac.uk/id/eprint/1399078/1/Sokal_130930133.pdf