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 edgesets partition the edgeset of G. This survey talk will present three of my favourite open problems in the area of graph decomposition. 1. A 1factor of a graph G is a 1regular spanning subgraph of G. A 1 factorisation of a graph G is a decomposition of G into 1factors. A perfect 1factorisation of a graph G is a 1factorisation of G in which the union of each pair of 1factors is a Hamilton cycle. The perfect 1 factorisation conjecture is that every complete graph of even order has a perfect 1factorisation. 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 1factor. 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 edgecolouring technique which shows that these conditions are sufficient for k = 1, 2 will be illustrated.
