Linear bound in terms of maxm axflow for the chromatic roots of series-parallel graphs

Gordon F. Royle; Alan D. Sokal

doi:10.1137/130930133

Linear bound in terms of maxm axflow for the chromatic roots of series-parallel graphs

Gordon F. Royle, Alan D. Sokal

Research output: Contribution to journal › Article › peer-review

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	https://doi.org/10.1137/130930133
State	Published - 2015

Keywords

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

ASJC Scopus subject areas

Mathematics(all)

Access to Document

10.1137/130930133

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

@article{bce26a7557e94305a9147a434b76b4e0,

title = "Linear bound in terms of maxm axflow for the chromatic roots of series-parallel graphs",

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 ≤ ve ≤ 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.",

keywords = "Antiferromagnetic potts model, Chromatic polynomial, Chromatic roots, Maxmaxflow, Multivariate tutte polynomial, Series-parallel graph",

author = "Royle, {Gordon F.} and Sokal, {Alan D.}",

note = "Publisher Copyright: {\textcopyright} 2015 Society for Industrial and Applied Mathematics.",

year = "2015",

doi = "10.1137/130930133",

language = "English (US)",

volume = "29",

pages = "2117--2159",

journal = "SIAM Journal on Discrete Mathematics",

issn = "0895-4801",

publisher = "Society for Industrial and Applied Mathematics Publications",

number = "4",

}

TY - JOUR

T1 - Linear bound in terms of maxm axflow for the chromatic roots of series-parallel graphs

AU - Royle, Gordon F.

AU - Sokal, Alan D.

PY - 2015

Y1 - 2015

N2 - 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 ≤ ve ≤ 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.

AB - 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 ≤ ve ≤ 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.

KW - Antiferromagnetic potts model

KW - Chromatic polynomial

KW - Chromatic roots

KW - Maxmaxflow

KW - Multivariate tutte polynomial

KW - Series-parallel graph

UR - http://www.scopus.com/inward/record.url?scp=84953307487&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84953307487&partnerID=8YFLogxK

U2 - 10.1137/130930133

DO - 10.1137/130930133

M3 - Article

AN - SCOPUS:84953307487

VL - 29

SP - 2117

EP - 2159

JO - SIAM Journal on Discrete Mathematics

JF - SIAM Journal on Discrete Mathematics

SN - 0895-4801

IS - 4

ER -

Linear bound in terms of maxm axflow for the chromatic roots of series-parallel graphs

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Cite this