Chromatic roots and hamiltonian paths

    Research output: Contribution to journalJournal articleResearchpeer-review


    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
    Issue number2
    Pages (from-to)218-224
    Publication statusPublished - Nov 2000


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

    Cite this