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.
Preview |
Text
Sokal_130930133.pdf - Published Version Download (1MB) | Preview |
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.
| Type: | Article |
|---|---|
| Title: | Linear Bound in Terms of Maxmaxflow for the Chromatic Roots of Series-Parallel Graphs |
| Open access status: | An open access version is available from UCL Discovery |
| DOI: | 10.1137/130930133 |
| Publisher version: | http://dx.doi.org/10.1137/130930133 |
| Language: | English |
| Additional information: | © 2015, Society for Industrial and Applied Mathematics. |
| 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 |
| UCL classification: | UCL UCL > Provost and Vice Provost Offices > UCL BEAMS UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences UCL > Provost and Vice Provost Offices > UCL BEAMS > Faculty of Maths and Physical Sciences > Dept of Mathematics |
| URI: | https://discovery.ucl.ac.uk/id/eprint/1399078 |
Loading...
Loading...Loading...Loading...Archive Staff Only
 |
View Item |
