Algebraic properties of chromatic roots

Peter J. Cameron, Kerri Morgan

    Research output: Contribution to journalArticleResearchpeer-review

    Abstract

    A chromatic root is a root of the chromatic polynomial of a graph. Any chromatic root is an algebraic integer. Much is known about the location of chromatic roots in the real and complex numbers, but rather less about their properties as algebraic numbers. This question was the subject of a seminar at the Isaac Newton Institute in late 2008. The purpose of this paper is to report on the seminar and subsequent developments. We conjecture that, for every algebraic integer α, there is a natural number n such that α+n is a chromatic root. This is proved for quadratic integers; an extension to cubic integers has been found by Adam Bohn. The idea is to consider certain special classes of graphs for which the chromatic polynomial is a product of linear factors and one “interesting” factor of larger degree. We also report computational results on the Galois groups of irreducible factors of the chromatic polynomial for some special graphs. Finally, extensions to the Tutte polynomial are mentioned briefly.

    Original languageEnglish
    Article number#P1.21
    Number of pages14
    JournalElectronic Journal of Combinatorics
    Volume24
    Issue number1
    Publication statusPublished - 3 Feb 2017

    Cite this

    Cameron, P. J., & Morgan, K. (2017). Algebraic properties of chromatic roots. Electronic Journal of Combinatorics, 24(1), [#P1.21].
    Cameron, Peter J. ; Morgan, Kerri. / Algebraic properties of chromatic roots. In: Electronic Journal of Combinatorics. 2017 ; Vol. 24, No. 1.
    @article{f502da391d754aff814d68a1db1bc2b8,
    title = "Algebraic properties of chromatic roots",
    abstract = "A chromatic root is a root of the chromatic polynomial of a graph. Any chromatic root is an algebraic integer. Much is known about the location of chromatic roots in the real and complex numbers, but rather less about their properties as algebraic numbers. This question was the subject of a seminar at the Isaac Newton Institute in late 2008. The purpose of this paper is to report on the seminar and subsequent developments. We conjecture that, for every algebraic integer α, there is a natural number n such that α+n is a chromatic root. This is proved for quadratic integers; an extension to cubic integers has been found by Adam Bohn. The idea is to consider certain special classes of graphs for which the chromatic polynomial is a product of linear factors and one “interesting” factor of larger degree. We also report computational results on the Galois groups of irreducible factors of the chromatic polynomial for some special graphs. Finally, extensions to the Tutte polynomial are mentioned briefly.",
    author = "Cameron, {Peter J.} and Kerri Morgan",
    year = "2017",
    month = "2",
    day = "3",
    language = "English",
    volume = "24",
    journal = "The Electronic Journal of Combinatorics",
    issn = "1077-8926",
    publisher = "Clemson University Digital Press",
    number = "1",

    }

    Cameron, PJ & Morgan, K 2017, 'Algebraic properties of chromatic roots' Electronic Journal of Combinatorics, vol. 24, no. 1, #P1.21.

    Algebraic properties of chromatic roots. / Cameron, Peter J.; Morgan, Kerri.

    In: Electronic Journal of Combinatorics, Vol. 24, No. 1, #P1.21, 03.02.2017.

    Research output: Contribution to journalArticleResearchpeer-review

    TY - JOUR

    T1 - Algebraic properties of chromatic roots

    AU - Cameron, Peter J.

    AU - Morgan, Kerri

    PY - 2017/2/3

    Y1 - 2017/2/3

    N2 - A chromatic root is a root of the chromatic polynomial of a graph. Any chromatic root is an algebraic integer. Much is known about the location of chromatic roots in the real and complex numbers, but rather less about their properties as algebraic numbers. This question was the subject of a seminar at the Isaac Newton Institute in late 2008. The purpose of this paper is to report on the seminar and subsequent developments. We conjecture that, for every algebraic integer α, there is a natural number n such that α+n is a chromatic root. This is proved for quadratic integers; an extension to cubic integers has been found by Adam Bohn. The idea is to consider certain special classes of graphs for which the chromatic polynomial is a product of linear factors and one “interesting” factor of larger degree. We also report computational results on the Galois groups of irreducible factors of the chromatic polynomial for some special graphs. Finally, extensions to the Tutte polynomial are mentioned briefly.

    AB - A chromatic root is a root of the chromatic polynomial of a graph. Any chromatic root is an algebraic integer. Much is known about the location of chromatic roots in the real and complex numbers, but rather less about their properties as algebraic numbers. This question was the subject of a seminar at the Isaac Newton Institute in late 2008. The purpose of this paper is to report on the seminar and subsequent developments. We conjecture that, for every algebraic integer α, there is a natural number n such that α+n is a chromatic root. This is proved for quadratic integers; an extension to cubic integers has been found by Adam Bohn. The idea is to consider certain special classes of graphs for which the chromatic polynomial is a product of linear factors and one “interesting” factor of larger degree. We also report computational results on the Galois groups of irreducible factors of the chromatic polynomial for some special graphs. Finally, extensions to the Tutte polynomial are mentioned briefly.

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

    M3 - Article

    VL - 24

    JO - The Electronic Journal of Combinatorics

    JF - The Electronic Journal of Combinatorics

    SN - 1077-8926

    IS - 1

    M1 - #P1.21

    ER -

    Cameron PJ, Morgan K. Algebraic properties of chromatic roots. Electronic Journal of Combinatorics. 2017 Feb 3;24(1). #P1.21.