Chromatic roots and hamiltonian paths

    Research output: Contribution to journalJournal articleResearchpeer-review

    Abstract

    We present a new connection between colorings and hamiltonian paths: If the chromatic polynomial of a graph has a noninteger root less than or equal to

    t(n) = 2/3 + 1/3 (3)root (26 + 6 root (33)) + 1/3 (3)root (26 - 6 root (33)) = 1.29559....

    then the graph has no hamiltonian path. This result is best possible in the sense that ii becomes false if t(0) is replaced by any larger number. (C) 2000 Academic Press.
    Original languageEnglish
    JournalJournal of Combinatorial Theory. Series B
    Volume80
    Issue number2
    Pages (from-to)218-224
    ISSN0095-8956
    DOIs
    Publication statusPublished - Nov 2000

    Fingerprint Dive into the research topics of 'Chromatic roots and hamiltonian paths'. Together they form a unique fingerprint.

    Cite this