Constructive resolution of two conjectures on real chromatic roots
Seminar Room 1, Newton Institute
In this talk I will discuss the recent resolution of two conjectures on the real roots of the chromatic polynomial of a graph, both of which were resolved by the construction of suitable families of graphs.
The first of these is Bill Jackson’s conjecture that 3connected nonbipartite graphs do not have chromatic roots in the interval (1,2), which turns out to be false. The counterexamples to this conjecture all have an intriguing connectivity property that seems unavoidable, lending support to a recent conjecture of Dong & Koh concerning graphs with no chromatic roots in (1,2).
The second conjecture that I discuss is Sami Beraha’s conjecture that there are planar graphs with real chromatic roots arbitrarily close to the point x = 4. For many years, the largest known real planar chromatic root was 3.8267 ...from a graph found by Douglas Woodall that appeared to have no obvious structure. However it turns out that viewed in the right way, this graph is the first member of an infinite sequence of graphs with real chromatic roots converging to 4.
The most wanted conjecture in the study of real chromatic roots is Birkhoff & Lewis’s conjecture that [4,5) is a rootfree interval for planar graphs, but unfortunately the resolution of Beraha’s conjecture appears to give no traction whatsoever on this conjecture.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.