School Seminars and Colloquia

Hadwiger's Graph Colouring Conjecture

Discrete Structures and Algorithms (Seminar)

by Dr David Wood

Institution: Mathematics and Statistics, The University of Melbourne
Date: Tue 16th March 2010
Time: 2:15 PM
Location: Room 215, Richard Berry Building, The University of Melbourne

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