Excessive Factorizations of Regular Graphs

An excessive factorization of a graph G is a minimum set F of1-factors of G whose union is E(G). In this paper we study excessive factorizations of regular graphs. We introduce two graph parameters related to excessive factorizations and show that their computation is NP-hard. We pose a number of questions regarding these parameters. We show that the size of an excessive factorization of a regular graph can exceed the degree of the graph by an arbitrarily large quantity. We conclude with a conjecture on the excessive factorizations of r-graphs.