Hadwiger's Graph Colouring Conjecture
by Dr David Wood
Abstract: Hadwiger's Conjecture is a sweeping generalisation of the
four-colour theorem for planar graphs, and is widely considered to be
one of the most important open problems in combinatorics. It states
that every graph containing no complete graph of order t as a minor
is (t-1)-colourable. The case t=5 implies the four-colour theorem.
The conjecture is known to be true for t <= 6, but is wide open for large t.
This talk will introduce graph colourings, graph minors, and Hadwiger's
Conjecture. I will conclude with some recent progress on a weakening of
Hadwiger's Conjecture that employs list colourings, some graph structure
theory, and a new sufficient condition for a graph to have a set of edges
whose contraction increases the connectivity.
For More Information: contact: Dr David Wood. email firstname.lastname@example.org