3
Constructive resolution of two conjectures on real chromatic roots
http://sms.cam.ac.uk/media/618
Royle, G (Western Australia)
Tuesday 22 January 2008, 10:0011:00
Zeros of Graph Polynomials
40
Constructive resolution of two conjectures on real chromatic roots
http://sms.cam.ac.uk/media/618
http://rss.sms.cam.ac.uk/itunesimage/1393615.jpg

Constructive resolution of two conjectures on real chromatic roots
ucs_sms_87_618
http://sms.cam.ac.uk/media/618
Constructive resolution of two conjectures on real chromatic roots
Royle, G (Western Australia)
Tuesday 22 January 2008, 10:0011:00
Zeros of Graph Polynomials
Fri, 01 Feb 2008 10:27:31 +0000
Steve Greenham
Royle, G
Isaac Newton Institute
Royle, G
2123a65c2ad09cbb8c158d9c1d80aac8
ebc8a769bb94c2ba65f0893cb496a542
cc996b234ad67fbeef184f67aaeb8663
d124ca1b57e43a81265e18b1b7ca37d4
15c64ab9fe19e992f632163a0a08d5a5
594f635f1ad7eb80cdddfd449872b11f
253d03b41f1ba32f9f5c6f5e31cd3ba9
Royle, G (Western Australia)
Tuesday 22 January 2008, 10:0011:00
Zeros of...
Royle, G (Western Australia)
Tuesday 22 January 2008, 10:0011:00
Zeros of Graph Polynomials
Cambridge University
3507
http://sms.cam.ac.uk/media/618
Constructive resolution of two conjectures on real chromatic roots
Royle, G (Western Australia)
Tuesday 22 January 2008, 10:0011:00
Zeros of Graph Polynomials
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.
Steve Greenham
http://sms.cam.ac.uk/person/sg438
20130328T14:35:30+00:00
3507
618
true
4x3
false