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 journalArticle

    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.

    Original languageEnglish (US)
    Pages (from-to)2117-2159
    Number of pages43
    JournalSIAM Journal on Discrete Mathematics
    Volume29
    Issue number4
    DOIs
    StatePublished - 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