9 - Recent results on chromatic and flow roots of graphs and matroids

Summary

Abstract

This paper surveys recent developments in the study of the real and complex roots of the chromatic and flow polynomials of graphs and matroids.

Introduction

The chromatic polynomial of a graph G is the polynomial P (G, q) that counts the number of proper q-colourings of G when q is a positive integer. It was introduced by Birkhoff [5] in 1912 in the hope that a quantitative study of the numbers of colourings of planar graphs might lead to an analytic proof of the 4-colour conjecture by demonstrating that P (G, 4) ≠ 0 whenever G is planar. Although originally defined only for positive integers q, it is well known that P (G, q) is a polynomial with integer coefficients (see for example, Read [41]) and although there may be no immediate combinatorial interpretation of the results, we can evaluate it at real or complex arguments and calculate its real or complex zeros. In this vein, Birkhoff and Lewis [4] showed that if G is a planar graph then P (G, q) ≥ 0 for all real q ≥ 5 and conjectured that the same result was true for real q ≥ 4. It is perhaps embarrassing that the very first conjecture on the location of real chromatic roots has still not been resolved more than sixty years later:

Conjecture 1.1 (The Birkhoff-Lewis Conjecture) If G is a planar graph then P (G, q) > 0 for all real q ≥ 4.