Projects per year
Abstract
The chromatic polynomial of a graph G is a univariate polynomial whose evaluation at any positive integer q enumerates the proper qcolourings 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 nontrivial chromatic root of a graph admitting a spanning tree with at most three leaves. Here, nontrivial 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 minorclosed 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 minorclosed classes of graphs and bipartite graphs.
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 nontrivial chromatic root of a graph admitting a spanning tree with at most three leaves. Here, nontrivial 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 minorclosed 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 minorclosed classes of graphs and bipartite graphs.
Original language  English 

Place of Publication  Kgs. Lyngby 

Publisher  Technical University of Denmark 
Number of pages  115 
Publication status  Published  2017 
Series  DTU Compute PHD2016 

Number  438 
ISSN  09093192 
Fingerprint
Dive into the research topics of 'Roots of the Chromatic Polynomial'. Together they form a unique fingerprint.Projects
 1 Finished

Chromatic Graph Theory
Perrett, T. (PhD Student), Thomassen, C. (Main Supervisor), Fischer, P. (Examiner), Kundgen, A. (Examiner) & Jackson, W. B. (Examiner)
01/10/2013 → 16/08/2017
Project: PhD