Linear Bound in Terms of Maxmaxflow for the Chromatic Roots of Series-Parallel Graphs

DOI10.1137/130930133zbMath1323.05071arXiv1307.1721OpenAlexW2107791854MaRDI QIDQ3449868

Gordon F. Royle, Alan D. Sokal

Publication date: 30 October 2015

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1307.1721

zbMATH Keywords

chromatic polynomialseries-parallel graphantiferromagnetic Potts modelchromatic rootsmultivariate Tutte polynomialmaxmaxflow

Mathematics Subject Classification ID

Related Items (7)

Chromatic zeros on hierarchical lattices and equidistribution on parameter space ⋮ Counting 2-connected deletion-minors of binary matroids ⋮ Approximating the chromatic polynomial is as hard as computing it exactly ⋮ On the location of chromatic zeros of series-parallel graphs ⋮ Location of zeros for the partition function of the Ising model on bounded degree graphs ⋮ Density of Real Zeros of the Tutte Polynomial ⋮ Algebraic properties of chromatic roots

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The Brown-Colbourn conjecture on zeros of reliability polynomials is false
• Maxmaxflow and counting subgraphs
• Zero-free regions for multivariate tutte polynomials (alias Potts-model partition functions) of graphs and matroids
• Chromatic roots - some observations and conjectures
• Automatic generation of linear-time algorithms from predicate calculus descriptions of problems on recursively constructed graph families
• Efficient graph representations
• Zeros of chromatic and flow polynomials of graphs
• On the Lambert \(w\) function
• Complex zero-free regions at large \(|q|\) for multivariate Tutte polynomials (alias Potts-model partition functions) with general complex edge weights
• Topology of series-parallel networks
• Recursive families of graphs
• Bounds on the Complex Zeros of (Di)Chromatic Polynomials and Potts-Model Partition Functions
• Absence of Zeros for the Chromatic Polynomial on Bounded Degree Graphs
• Regions Without Complex Zeros for Chromatic Polynomials on Graphs with Bounded Degree
• The Recognition of Series Parallel Digraphs
• Graph Classes: A Survey
• Location of Zeros of Chromatic and Related Polynomials of Graphs
• The Zero-Free Intervals for Chromatic Polynomials of Graphs
• Zeros of Reliability Polynomials and f-vectors of Matroids
• Linear-time computation of optimal subgraphs of decomposable graphs
• Chromatic Roots are Dense in the Whole Complex Plane
• The Random-Cluster Model
• Chromatic Polynomials
• Parallel algorithms for series parallel graphs and graphs with treewidth two

This page was built for publication: Linear Bound in Terms of Maxmaxflow for the Chromatic Roots of Series-Parallel Graphs