Algebraic Graph Theory Seminar - Gordon Royle

Monday, February 22, 2021 6:00 pm - 6:00 pm EST (GMT -05:00)

*Note different start time

Title: Real Chromatic Roots of Graphs

Speaker: Gordon Royle
Affiliation: The University of Western Australia
Zoom: Contact Soffia Arnadottir

Abstract:

In February 1988, I arrived at C&O Waterloo for a postdoc with the late Ron Read. He handed me a paper by Beraha, Kahane and Weiss, and told me to apply it to determining the location of the complex roots of chromatic polynomials.  I’ve returned to the topic every few years since then, with varying degrees of success---some positive results, but still many open problems and conjectures remain.

The chromatic polynomial P(G,q) of a graph G is the function that, for positive integer q,  counts the number of proper q-colourings of the graph. The resulting function is a polynomial so, whether or not it makes any combinatorial sense, we can evaluate it at any complex number and therefore find its roots which may be integer, real of complex.  The aim is to understand the relationship between the properties of a graph and the location of its chromatic roots.

In this talk, I will just focus on the real roots of chromatic polynomials, describing a few of the results, conjectures, and open problems to which I periodically return. The only things I will assume about the audience are that they know the definition of a graph, a proper colouring and a polynomial, and that they are willing to sit through a talk where the word “quantum” does not occur even once.