School Seminars and Colloquia

Characterizations and algorithms for topological containment of wheel graphs

Discrete Structures and Algorithms (Seminar)

by Rebecca Robinson


Institution: Monash University
Date: Tue 15th September 2009
Time: 2:15 PM
Location: Room 107, Richard Berry Building, The University of Melbourne

Abstract: Topological containment is an important substructure relation in graph theory. A graph G is
said to topologically contain another pattern graph H if a graph isomorphic to H can be
obtained from G by performing a series of deletions and contractions, where contractions are
limited to edges with at least one endvertex of degree 2.


The problem of topological containment has been shown by Robertson and Seymour to be
polynomial-time solvable for any fixed pattern graph. However, practical characterizations
and algorithms have only been developed for a few small pattern graphs. In this talk, I will
look at some previous results on topological containment for particular pattern graphs. I will
also talk about two new results: one characterizing graphs that do not topologically contain
the wheel with six spokes, and one that gives a characterization (up to bounded size pieces)
of graphs that do not topologically contain the wheel with seven spokes.

For More Information: contact: David Wood. email: woodd@unimelb.edu.au