Seminars

12 noon Tuesday 27 July 2010, Seminar room M345
School of Mathematical Sciences Seminar
Graph decomposition problems
Dr Daniel Horsley (Department of Mathematics and Statistics, Memorial University of Newfoundland)

Graph decomposition problems are a class of combinatorial problems that arise at the boundary of graph theory and design theory. They are concerned with when a graph can be formed as an edge-disjoint union of smaller graphs satisfying various specified conditions.  Such problems are very difficult in general, but when strong restrictions are placed on the big graph and/or the smaller graphs the problems can become tractable and have received intensive study.  In this talk I will give an introduction to graph decomposition problems, considering their relationship to famous problems in combinatorics as well as their practical applications.  I will also discuss some of my own research on problems in this area.