Constructive resolution of two conjectures on real chromatic roots

58 mins 27 secs, 808.35 MB, MPEG-4 Video 480x360, 25.0 fps, 44100 Hz, 1.84 Mbits/sec

About this item

Description:	Royle, G (Western Australia) Tuesday 22 January 2008, 10:00-11:00 Zeros of Graph Polynomials

Created:

2008-02-01 10:27

Collection:

Combinatorics and Statistical Mechanics

Publisher:

Isaac Newton Institute

Royle, G

Language:

eng (English)

Credits:

Author:	Royle, G
Producer:	Steve Greenham


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.

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.

Available Formats

Format	Quality	Bitrate	Size
MPEG-4 Video *	480x360	1.84 Mbits/sec	808.35 MB	View	Download
Flash Video	480x360	806.52 kbits/sec	345.86 MB	View	Download
iPod Video	480x360	505.3 kbits/sec	216.69 MB	View	Download
Windows Media Video (for download)	480x360	477.46 kbits/sec	204.75 MB	View	Download
Windows Media Video (for streaming)	480x360	447.08 kbits/sec	191.72 MB	View	Download	Stream
RealMedia	480x360	878.16 kbits/sec	376.59 MB	View	Download	Stream
QuickTime (for download)	384x288	848.47 kbits/sec	363.85 MB	View	Download
QuickTime (for streaming)	480x360	907.06 kbits/sec	388.98 MB	View	Download
MP3	44100 Hz	125.02 kbits/sec	53.40 MB	Listen	Download