PhD Defence by Thomas Perrett, Friday 20 January 2017 at 13:00, Technical University of Denmark (DTU), Building 101, Meeting Center room S09.
Read more about this thesis in DTU Orbit.
Supervisor: Professor Carsten Thomassen, DTU Compute.
Examiners:
Associate Professor Paul Fischer, DTU Compute (Chair).
Professor William Bill Jackson, Queen Mary University of London, UK.
Professor André Kündgen, California State University San Marcos, USA.
Chairman of the proceedings:
Associate Professor Poul G Hjorth, DTU Compute
Everyone is welcome
Abstract: We are surrounded by networks of all conceivable types: Road networks, computer networks, social networks,
and more. Even abstract physical principles such as ferromagnetism can be modelled by a network
of particles and charges. When we take such a network and strip away any additional information so that
only the structure remains, we are left with the mathematical notion of a graph. The study of graphs is the
subject of this thesis.
More specifically, we focus on graph colouring: a common problem with many applications. Loosely speaking,
the aim is to partition a graph into several parts, so that there are no connections within each part.
Whether this is possible, and in how many ways it can be done, is encoded in the roots and evaluations of
a polynomial called the chromatic polynomial. The main results of this thesis deal with roots of the chromatic
polynomial, and how they vary depending on certain graph properties.
We first prove lower bounds on the smallest roots of the chromatic polynomial when the graph in question
has a variety of structural properties. Then, for historical reasons, we investigate the chromatic polynomials
of graphs that can be drawn on a sphere such that no edges cross. In this case we deduce a density
result for real roots of the chromatic polynomial between 3 and 4, but a surprising gap emerges due to a
famous theorem of Tutte involving the golden ratio. Finally, we investigate the Tutte polynomial, which is a
generalisation of the chromatic polynomial, and deduce a density result for its roots.