# 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 woodd@unimelb.edu.au