Algebraic properties of chromatic roots

Peter Jephson Cameron, Kerri Morgan

Research output: Contribution to journalArticlepeer-review

6 Citations (Scopus)

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 alpha, there is a
natural number n such that alpha+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 numberP1.21
Number of pages14
JournalElectronic Journal of Combinatorics
Volume24
Issue number1
Publication statusPublished - 3 Feb 2017

Keywords

  • chromatic polynomial, Galois group, algebraic integer

Fingerprint

Dive into the research topics of 'Algebraic properties of chromatic roots'. Together they form a unique fingerprint.

Cite this