The INI has a new website!

This is a legacy webpage. Please visit the new site to ensure you are seeing up to date information.

Skip to content

CSM

Seminar

Constructive resolution of two conjectures on real chromatic roots

Royle, G (Western Australia)
Tuesday 22 January 2008, 10:00-11:00

Seminar Room 1, Newton Institute

Abstract

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.

Presentation

[pdf ]

Audio

MP3MP3

Video

The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.

Back to top ∧