SEMINAR: Groups and Combinatorics Seminar: Decomposition theorems for graphs and matroids

Time and place: 15:00 Friday 30 October in Weatherburn LT.

Speaker: Irene Pivotto (University of Western Australia)

Title: Decomposition theorems for graphs and matroids

Abstract: Wagner proved that every graph that does not contain a clique on 5 vertices as a minor may be constructed by glueing together (in specified ways) planar graphs and copies of a specific graph. This is a prototypical example of a decomposition theorem: a result that explains how to construct all graphs in a class by glueing together graphs in well-understood classes and graphs from some finite set. Besides being useful tools in proving properties of decomposable graphs, these types of theorems have algorithmic consequences.

In this talk I will present some interesting decomposition theorems for graphs and matroids and discuss some progress toward proving a new result of this type.