It is proved that the chromatic polynomial of a connected graph with n vertices and m edges has a root with modulus at least (m&1)Γ(n&2); this bound is best possible for trees and 2-trees (only). It is also proved that the chromatic polynomial of a graph with few triangles that is not a forest has a nonreal root and that there is a graph with n vertices whose chromatic polynomial has a root with imaginary part greater than -nΓ4.
1998 Academic Press
1. Introduction
Let ?(G, x) and /(G) denote respectively the chromatic polynomial and chromatic number of a graph G with n vertices and m edges. A number of papers have considered the location of the roots of the chromatic polynomial of a graph. Birkhoff and Lewis showed that the chromatic polynomial of any plane triangulation has no roots in the intervals (& , 0), (0, 1), (1, 2), and ), and Woodall [22] improved this by showing that in fact there are no roots in (2, 2.546602...) (the latter being the smallest nonintegral real root of the chromatic polynomial of the octahedron). It is well known (see ) that no graph has a root of its chromatic polynomial in (& , 0) or (0, 1). Jackson proved that no graph has a root of its chromatic polynomial in the interval (1, 32Γ27], and Thomassen has shown that Jackson's result is best possible, in that for any *>32Γ27, there is a graph whose chromatic polynomial has a root arbitrary close to *.
Regarding the locations of chromatic roots (i.e., roots of chromatic polynomials) in the complex plane, there are relatively few results and many conjectures (cf. [4, 5, 8, 11, 16, 17, 21]). Read and Royle have calculated the chromatic roots of many small graphs, and the structure of these roots is still elusive. The limit points of the chromatic roots of a few special classes of graphs have been determined . it was proved that all the roots of ?(G, x) lie within the disk |z&1| m&n+1;