Roots of the Chromatic Polynomial

The chromatic polynomial of a graph G is a univariate polynomial whose evaluation at any positive integer q enumerates the proper q-colourings of G. It was introduced in connection with the famous four colour theorem but has recently found other applications in the field of statistical physics. In this thesis we study the real roots of the chromatic polynomial, termed chromatic roots, and focus on how certain properties of a graph affect the location of its chromatic roots.

Firstly, we investigate how the presence of a certain spanning tree in a graph affects its chromatic roots. In particular we prove a tight lower bound on the smallest non-trivial chromatic root of a graph admitting a spanning tree with at most three leaves. Here, non-trivial means different from 0 or 1.

This extends a theorem of Thomassen on graphs with Hamiltonian paths. We also prove similar lower bounds on the chromatic roots of certain minor-closed families of graphs. Later, we study the Tutte polynomial of a graph, which contains the chromatic polynomial as a specialisation. We discuss a technique of Thomassen using which it is possible to deduce that the roots of the chromatic polynomial are dense in certain intervals.

We extend Thomassen’s technique to the Tutte polynomial and as a consequence, deduce a density result for roots of the Tutte polynomial. This partially answers a conjecture of Jackson and Sokal. Finally, we refocus our attention on the chromatic polynomial and investigate the density of chromatic roots of several graph families.

In particular, we show that the chromatic roots of planar graphs are dense in the interval (3; 4), except for a small interval around _ + 2 _ 3:618, where _ denotes the golden ratio. We also investigate the chromatic roots of related minor-closed classes of graphs and bipartite graphs.