On the chromatic roots of generalized theta graphs

Jason I. Brown, Carl Hickman, Alan D. Sokal, David G. Wagner

    Research output: Contribution to journalArticle

    Abstract

    The generalized theta graph χS1,⋯,Sk consists of a pair of endvertices joined by k internally disjoint paths of lengths S1,⋯,Sk≥1. We prove that the roots of the chromatic polynomial π(χS1,⋯,Sk, Z) of a k-ary generalized theta graph all lie in the disc z - 1 ≤ [ 1 + o (1) ]k/log k, uniformly in the path lengths Si. Moreover, we prove that χ2,⋯,2≃K2 indeed has a chromatic root of modulus [1+0(1)]k/log k. Finally, for k ≤ 8 we prove that the generalized theta graph with a chromatic root that maximizes z - 1 is the one with all path lengths equal to 2; we conjecture that this holds for all k.

    Original languageEnglish (US)
    Pages (from-to)272-297
    Number of pages26
    JournalJournal of Combinatorial Theory. Series B
    Volume83
    Issue number2
    DOIs
    StatePublished - 2001

    Keywords

    • Chromatic polynomial
    • Chromatic roots
    • Complete bipartite graph
    • Generalized theta graph
    • Graph
    • Lambert W function
    • Potts model
    • Series-parallel graph

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Discrete Mathematics and Combinatorics
    • Computational Theory and Mathematics

    Fingerprint Dive into the research topics of 'On the chromatic roots of generalized theta graphs'. Together they form a unique fingerprint.

  • Cite this