Discrete Mathematics & Theoretical Computer Science |
A chromatic root is a zero of the chromatic polynomial of a graph. At a Newton Institute workshop on Combinatorics and Statistical Mechanics in 2008, two conjectures were proposed on the subject of which algebraic integers can be chromatic roots, known as the ``$α +n$ conjecture'' and the ``$nα$ conjecture''. These say, respectively, that given any algebraic integer α there is a natural number $n$ such that $α +n$ is a chromatic root, and that any positive integer multiple of a chromatic root is also a chromatic root. By computing the chromatic polynomials of two large families of graphs, we prove the $α +n$ conjecture for quadratic and cubic integers, and show that the set of chromatic roots satisfying the nα conjecture is dense in the complex plane.