## 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.

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 language | English |
---|---|

Article number | P1.21 |

Number of pages | 14 |

Journal | Electronic Journal of Combinatorics |

Volume | 24 |

Issue number | 1 |

Publication status | Published - 3 Feb 2017 |

## Keywords

- chromatic polynomial, Galois group, algebraic integer