Speaker: Barbara Maenhaut
The University of Queensland, Queensland, Australia, 4072
Topic: Graph decompositions and factorisations
Abstract: A decomposition of a graph G is a set of subgraphs of G whose edge-sets partition the edge-set of G. This survey talk will present three of my favourite open problems in the area of graph decomposition.
1. A 1-factor of a graph G is a 1-regular spanning subgraph of G. A 1- factorisation of a graph G is a decomposition of G into 1-factors. A perfect 1-factorisation of a graph G is a 1-factorisation of G in which the union of each pair of 1-factors is a Hamilton cycle. The perfect 1- factorisation conjecture is that every complete graph of even order has a perfect 1-factorisation. A summary of recent results on this conjecture will be presented.
2. Given a list of positive integers m1,m2, . . . ,mt and a positive odd integer n, Alspach’s cycle decomposition problem asks for a decomposition of the complete graph of order n into cycles of lengths m1,m2, . . . ,mt whenever the obvious necessary conditions are satisfied. In the case of the complete graph of even order, the problem asks for a decomposition into cycles of specified lengths and a 1-factor. Recent progress on this problem and its generalisations will be presented.
3. For which positive integers k, n,m1,m2, . . . ,mt does there exist a decomposition of some subgraph of the complete graph of order n into k- regular subgraphs of orders m1,m2, . . . ,mt? Some necessary conditions on k, n,m1,m2, . . . ,mt will be presented and an edge-colouring technique which shows that these conditions are sufficient for k = 1, 2 will be illustrated.