### Abstract

We prove that the (real or complex) chromatic roots of a series-parallel graph with maxmaxflow ? lie in the disc |q - 1| < (∧ - 1)/log2. 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 ≤ v_{e} ≤ 0. For each ∧ ≥ 3, we exhibit a family of graphs, namely, the "leaf-joined trees", with maxmaxflow ? and chromatic roots accumulating densely on the circle |q - 1| = ∧ - 1, thereby showing that our result is within a factor 1/log 2 ≈ 1.442695 of being sharp.

Original language | English (US) |
---|---|

Pages (from-to) | 2117-2159 |

Number of pages | 43 |

Journal | SIAM Journal on Discrete Mathematics |

Volume | 29 |

Issue number | 4 |

DOIs | |

State | Published - 2015 |

### Keywords

- Antiferromagnetic potts model
- Chromatic polynomial
- Chromatic roots
- Maxmaxflow
- Multivariate tutte polynomial
- Series-parallel graph

### ASJC Scopus subject areas

- Mathematics(all)

## Fingerprint Dive into the research topics of 'Linear bound in terms of maxm axflow for the chromatic roots of series-parallel graphs'. Together they form a unique fingerprint.

## Cite this

Royle, G. F., & Sokal, A. D. (2015). Linear bound in terms of maxm axflow for the chromatic roots of series-parallel graphs.

*SIAM Journal on Discrete Mathematics*,*29*(4), 2117-2159. https://doi.org/10.1137/130930133