Chromatic roots as algebraic integers
Abstrak
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.
Topik & Kata Kunci
Penulis (1)
Adam Bohn
Akses Cepat
- Tahun Terbit
- 2012
- Sumber Database
- DOAJ
- DOI
- 10.46298/dmtcs.3061
- Akses
- Open Access ✓